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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Existence of a Substring in a String and Its Reverse

Number: 3353

Difficulty: Easy

Paid? No

Companies: Rubrik

Problem Description

Given a string s, determine whether there exists any substring of length 2 from s that also appears in the reverse of s. Return true if such a substring exists; otherwise, return false.

Key Insights

  • We only need to compare substrings of length 2.
  • The reverse of s is just s read from end to beginning.
  • Use a hash set (or similar structure) to store all consecutive 2-letter substrings from s and its reverse.
  • Comparing these sets (or checking membership) allows an efficient O(n) solution where n is the length of s.
  • Edge case: If s has less than 2 characters, the answer is false.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(n), used for storing up to n-1 substrings from s and its reverse.

Solution

We first check if s has at least 2 characters. Then, we generate a set of all adjacent 2-character substrings for s and do the same for its reverse. Finally, we check if there is any common substring between these two sets. This approach leverages hash tables (sets) for efficient lookup. One trick is to use built-in string reversal methods and set operations to simplify the intersection check.

Code Solutions

# Function to check if there's any common 2-letter substring in s and its reverse.
def exists_common_substring(s: str) -> bool:
    # If string length is less than 2, no such substring exists.
    if len(s) < 2:
        return False

    # Generate all substrings of length 2 for the original string.
    substrings = {s[i:i+2] for i in range(len(s) - 1)}
    # Reverse the string.
    reverse_s = s[::-1]
    # Generate all substrings of length 2 for the reversed string.
    reverse_substrings = {reverse_s[i:i+2] for i in range(len(reverse_s) - 1)}

    # Check if there's any common substring between the two sets.
    return len(substrings.intersection(reverse_substrings)) > 0

# Example usage:
print(exists_common_substring("leetcode"))  # Expected output: True
print(exists_common_substring("abcd"))      # Expected output: False
← Back to All Questions