#3083

Easy

LeetCode Problem Workspace

Existence of a Substring in a String and Its Reverse

Check for any substring of length 2 in a string and its reverse using a hash table and string comparison.

Problem Statement

You are given a string s. Your task is to find any substring of length 2 in the string that also appears in the reverse of the string.

Return true if such a substring exists, and false otherwise. The task can be optimized using a hash table to store substrings for quick look-up during comparison.

Examples

Example 1

Input: s = "leetcode"

Output: true

Substring "ee" is of length 2 which is also present in reverse(s) == "edocteel" .

Example 2

Input: s = "abcba"

Output: true

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

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.

Solution Approach

Reverse the String

First, create a reversed version of the string. This will help to compare substrings of the original string with those in the reversed string efficiently.

Hash Table for Substrings

Use a hash table to store all substrings of length 2 from the original string. Then check if any of these substrings appear in the reversed string.

Efficient Comparison

For each substring in the hash table, check if it also exists in the reversed string. This comparison can be done efficiently due to the use of the hash table.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the method used for substring generation and comparison. Creating substrings takes O(n) time where n is the length of the string. Checking each substring against the reversed string can also be done in O(n) time using the hash table, resulting in an overall time complexity of O(n). The space complexity is O(n) due to the storage of substrings in the hash table.

What Interviewers Usually Probe

Can the candidate efficiently implement a hash table-based solution?
Does the candidate show an understanding of string reversal and substring comparison?
Is the candidate able to optimize the solution with respect to time and space complexity?

Common Pitfalls or Variants

Common pitfalls

Not reversing the string before comparison, which leads to incorrect results.
Incorrectly checking substrings, leading to missing valid matches.
Using inefficient data structures for substring lookup, causing slower solutions.

Follow-up variants

Consider substrings of length 3 instead of 2.
Check if there are any substrings of length 2 that are palindromes.
Optimize the solution by reducing the space complexity of the hash table.

FAQ

How can I solve "Existence of a Substring in a String and Its Reverse" efficiently?

You can solve this by reversing the string, storing substrings of length 2 in a hash table, and checking if any of those substrings appear in the reversed string.

What is the time complexity of the solution for "Existence of a Substring in a String and Its Reverse"?

The time complexity is O(n), where n is the length of the string, due to substring generation and comparison using a hash table.

What are some common mistakes when solving "Existence of a Substring in a String and Its Reverse"?

Common mistakes include not reversing the string, incorrectly comparing substrings, and using inefficient data structures for substring lookup.

Can the solution for "Existence of a Substring in a String and Its Reverse" be optimized?

Yes, you can optimize the solution by reducing space complexity in the hash table and ensuring efficient string comparison.

Is there a way to check substrings of a different length in "Existence of a Substring in a String and Its Reverse"?

Yes, you can modify the problem to check for substrings of any length, such as 3 or more, by adjusting the substring generation and comparison logic.

terminal

Solution

Solution 1: Hash Table or Array

We can use a hash table or a two-dimensional array $st$ to store all substrings of length $2$ of the reversed string $s$.

1

2

3

4

class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        st = {(a, b) for a, b in pairwise(s[::-1])}
        return any((a, b) in st for a, b in pairwise(s))

Continue Practicing

#3081 replace question marks in string to minimize its value #3085 minimum deletions to make string k special #3076 shortest uncommon substring in an array