Teaching Kids Programming – Existence of a Substring in a String and Its Reverse

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, find any substring of length 2 which is also present in the reverse of s. Return true if such a substring exists, and false otherwise.

Example 1:
Input: s = “leetcode”
Output: true
Explanation: Substring “ee” is of length 2 which is also present in reverse(s) == “edocteel”.

Example 2:
Input: s = “abcba”
Output: true
Explanation: All of the substrings of length 2 “ab”, “bc”, “cb”, “ba” are also present in reverse(s) == “abcba”.

Example 3:
Input: s = “abcd”
Output: false
Explanation: There is no substring of length 2 in s, which is also present in the reverse of s.

Constraints:
1 <= s.length <= 100
s consists only of lowercase English letters.

Hints:
Make a new string by reversing the string s.
For every substring of length 2 in s, check if there is a corresponding substring in the reverse of s.

Existence of a Substring in a String and Its Reverse

This is a easy question, which can be solved using multiple algorithms.

Brutefore Algorithm: All Pairs of Substring Size Two

The easiest solution would be to iterate over the pairs of substring of size 2 and compare each. This takes O(N^2) quadratic time, and O(1) constant space.

1
2
3
4
5
6
7
8
9

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        ## BruteForce O(N^2) Time, O(1) Space
        n = len(s)
        for i in range(n - 1):
            for j in range(n - 1):
                if (s[i], s[i + 1]) == (s[j + 1], s[j]):
                    return True
        return False

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        ## BruteForce O(N^2) Time, O(1) Space
        n = len(s)
        for i in range(n - 1):
            for j in range(n - 1):
                if (s[i], s[i + 1]) == (s[j + 1], s[j]):
                    return True
        return False

We can use the itertools.pairwise as a syntax sugar to make the implementation a bit concise:

1
2
3
4
5
6
7

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        for x, y in pairwise(s):
            for b, a in pairwise(s):
                if  x == a and y == b:
                    return True
        return False

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        for x, y in pairwise(s):
            for b, a in pairwise(s):
                if  x == a and y == b:
                    return True
        return False

The inner loop check can be done by the “in” operation which performs a substring search – O(N) linear search.

1
2
3
4
5
6

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        for x, y in pairwise(s):
            if y + x in s:
                return True
        return False

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        for x, y in pairwise(s):
            if y + x in s:
                return True
        return False

The one-liner:

1
2
3

return any(s[i:i+2] in s[::-1] for i in range(len(s) - 1))
return any(y + x in s for x, y in pairwise(s))
return any(x + y in s[::-1] for x, y in pairwise(s))

return any(s[i:i+2] in s[::-1] for i in range(len(s) - 1))
return any(y + x in s for x, y in pairwise(s))
return any(x + y in s[::-1] for x, y in pairwise(s))

Using Hash Map/Set to Speed up Search

We can remember the (x, y) substring of 2 in a hash map/set, and thus, the lookup can be improved to O(1) constant. The time/space complexity is O(N).

1
2
3
4
5
6
7
8

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        seen = set()
        for x, y in pairwise(s):
            seen.add((x, y))
            if (y, x) in seen:
                return True
        return False   

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        seen = set()
        for x, y in pairwise(s):
            seen.add((x, y))
            if (y, x) in seen:
                return True
        return False   

–EOF (The Ultimate Computing & Technology Blog) —