Existence of a Substring in a String and Its Reverse Python/Java solution

Most implementations follow the same pattern: iterate through the string, store two-character substrings in a set, and check whether the reversed pair exists. This logic translates directly across Python, Java, C++, and other languages with built-in hash set support.

How to solve Existence of a Substring in a String and Its Reverse in O(n)?

Scan the string and extract every substring of length two. Insert each substring into a hash set and check whether its reversed form already exists. Since insertion and lookup in a hash table are constant time on average, the entire process completes in linear O(n) time.

What is the best approach for Existence of a Substring in a String and Its Reverse?

The most efficient approach uses a hash set. Iterate through the string, store every substring of length two, and check whether the reversed pair already exists in the set. This gives O(n) time complexity with O(n) extra space and is the solution typically expected in coding interviews.

Is Existence of a Substring in a String and Its Reverse asked at Google/Amazon/Meta?

Problems like this appear frequently in interviews at large tech companies because they test string traversal and hash-table usage. While this exact problem is from LeetCode, similar substring detection and pattern-matching questions show up in interviews at companies like Amazon, Google, and Meta.

What data structure is used in Existence of a Substring in a String and Its Reverse?

A hash set (or hash table) is the primary data structure used in the optimal solution. It stores previously seen substrings and enables constant-time checks to determine whether the reverse of the current substring already exists.

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

The optimal hash-set approach runs in O(n) time because the string is scanned once and each substring lookup is O(1). Space complexity is O(n) for storing substrings. A sorting-based method exists but increases the time complexity to O(n log n).

Description Hints 2 Solution Video 2:57

3083. Existence of a Substring in a String and Its Reverse

Q: Is Existence of a Substring in a String and Its Reverse easy or hard?

The problem is categorized as Easy on LeetCode with an acceptance rate above 60%. It focuses on basic string iteration and hash-set usage, making it a common warm-up problem for practicing string and hash table concepts.

Easy66.6% acceptance1 company

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.

Asked at 1 company

Rubrik

Topics

Hash Table String

Hints open one at a time

Hint 1

Make a new string by reversing the string s.

Hint 2

For every substring of length 2 in s, check if there is a corresponding substring in the reverse of s.

2:57

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def isSubstringPresent(self, s: str) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"leetcode"

Input

"abcba"

Input

"abcd"

Your code is saved on this device.Solution