Existence of a Substring in a String and Its Reverse

Difficulty: Easy | Acceptance: 66.50% | Paid: No Topics: Hash Table, String

Given a string s, return true if a substring of s of length at least 2 is also a substring of the reverse of s. Otherwise, return false.

• Examples
• Constraints
• Brute Force (All Substrings)
• Hash Set (Length 2 Optimization)
• Boolean Array (Fixed Space)

Examples

Input: s = "leetcode"
Output: true
Explanation: The substring "et" appears in s and also appears in the reverse of s ("edocteel").

Input: s = "abcba"
Output: true
Explanation: The substring "bc" appears in s and also appears in the reverse of s ("abcba").

Input: s = "abcd"
Output: false
Explanation: There is no substring of length at least 2 that appears in s and its reverse.

Constraints

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

Brute Force (All Substrings)

Intuition We can generate all possible substrings of length 2 or more from the original string and store them in a set. Then, we generate all substrings from the reversed string and check if any exist in the set.

Steps

• Reverse the input string s to get rev.
• Initialize a hash set to store substrings.
• Iterate through s with two loops to generate all substrings of length >= 2 and add them to the set.
• Iterate through rev with two loops to generate all substrings of length >= 2.
• If any substring from rev is found in the set, return true.
• If the loop finishes without a match, return false.

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        rev = s[::-1]
        substrings = set()
        n = len(s)
        
        for i in range(n):
            for j in range(i + 2, n + 1):
                substrings.add(s[i:j])
                
        for i in range(n):
            for j in range(i + 2, n + 1):
                if rev[i:j] in substrings:
                    return True
                    
        return False

Complexity

• Time: O(n³) - Generating all substrings takes O(n²) and string slicing/copying takes O(n) in worst case.
• Space: O(n³) - Storing all substrings requires O(n³) space in worst case.
• Notes: Simple but inefficient for larger strings.

Hash Set (Length 2 Optimization)

Intuition If a substring of length k exists in both s and reverse(s), then its prefix of length 2 must also exist in both. Therefore, we only need to check for common substrings of length exactly 2.

Steps

• Initialize a hash set to store all length-2 substrings of s.
• Iterate through s and add every pair of adjacent characters s[i]s[i+1] to the set.
• Iterate through s again and check if the reverse pair s[i+1]s[i] exists in the set.
• If found, return true.
• If the loop finishes, return false.

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        seen = set()
        n = len(s)
        
        for i in range(n - 1):
            seen.add(s[i:i+2])
            
        for i in range(n - 1):
            if s[i+1] + s[i] in seen:
                return True
                
        return False

Complexity

• Time: O(n) - We iterate through the string a constant number of times.
• Space: O(n) - The set can store up to n-1 substrings.
• Notes: Efficient time complexity with linear space usage.

Boolean Array (Fixed Space)

Intuition Since the string consists only of lowercase English letters, there are only 26 * 26 = 676 possible pairs of characters. We can use a fixed-size boolean array to track seen pairs, achieving O(1) space.

Steps

• Initialize a boolean array of size 676 (26*26) to false.
• Iterate through s to calculate a unique index for each pair s[i]s[i+1] using the formula (c1 - 'a') * 26 + (c2 - 'a'). Mark this index as true.
• Iterate through s again and calculate the index for the reverse pair s[i+1]s[i].
• If the index for the reverse pair is already true, return true.
• If the loop finishes, return false.

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        seen = [False] * 26 * 26
        n = len(s)
        
        for i in range(n - 1):
            idx = (ord(s[i]) - 97) * 26 + (ord(s[i+1]) - 97)
            seen[idx] = True
            
        for i in range(n - 1):
            rev_idx = (ord(s[i+1]) - 97) * 26 + (ord(s[i]) - 97)
            if seen[rev_idx]:
                return True
                
        return False

Complexity

• Time: O(n) - Linear scan of the string.
• Space: O(1) - The boolean array size is fixed at 676, regardless of input size.
• Notes: Most optimal solution for this specific problem constraints.