We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Existence of a Substring in a String and Its Reverse

Difficulty: Easy

Problem Description

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.

Key Insights

  • A substring of length 2 consists of two consecutive characters.
  • The reverse of a string can be easily obtained.
  • We need to check for common substrings of length 2 between the original string and its reverse.
  • A hash table can be used to efficiently store and check for the existence of these substrings.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. We traverse the string to create substrings and check them against the reverse. Space Complexity: O(n), for storing the substrings in a hash table.

Solution

To solve the problem, we can use the following approach:

  1. Generate all possible substrings of length 2 from the original string s and store them in a hash table (or set).
  2. Generate the reverse of the string s.
  3. Check if any of the substrings of length 2 from the original string exist in the substrings of the reversed string.
  4. If a match is found, return true; otherwise, return false.

This approach leverages the efficiency of hash tables for quick lookups.

Code Solutions

def has_common_substring(s: str) -> bool:
    substrings = set()
    
    # Store all substrings of length 2 in a set
    for i in range(len(s) - 1):
        substrings.add(s[i:i + 2])
    
    # Generate the reversed string
    reversed_s = s[::-1]
    
    # Check for common substrings in the reversed string
    for i in range(len(reversed_s) - 1):
        if reversed_s[i:i + 2] in substrings:
            return True
            
    return False
← Back to All Questions