Existence of a Substring in a String and Its Reverse Solution
Existence of a Substring in a String and Its Reverse solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Existence of a Substring in a String and Its Reverse is an easy coding problem on strings and hash table, asked in Amazon, Google, Cognizant and Rubrik interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table
- Asked at: Amazon, Google, Cognizant, Rubrik
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return true if any substring of s of length 2 also occurs in the reverse of s, and false otherwise.
Example 1
Input: s = "reedkairo"
Output: true
Explanation: `ee` occurs in the reverse `oriakdeer`.
Example 2
Input: s = "codekairo"
Output: false
Explanation: None of `co`, `od`, `de`, `ek`, `ka`, `ai`, `ir`, `ro` survives the reversal.
Example 3
Input: s = "abcba"
Output: true
Explanation: `bc` occurs in the reverse, which is the same string.
Constraints
1 <= s.length <= 100s consists only of lowercase English letters.
Hints for Existence of a Substring in a String and Its Reverse
Hint 1
A pair
xyappears in the reverse ofsexactly whenyxappears ins.Hint 2
So you never need to build the reversed string at all.
Hint 3
For every adjacent pair, look for its flip anywhere in
s.
How to solve Existence of a Substring in a String and Its Reverse
Reversing s maps a substring xy to yx, so xy occurs in the reverse precisely when yx occurs in s. Check each adjacent pair's flip against the original string.
Approach
- For each
i, form the flipped pairs[i+1] + s[i]. - If that pair occurs anywhere in
s, returntrue. - Return
falseif none does.
Why it works
The flip identity is what removes the reversal entirely — building the reversed string and searching it would work but doubles the memory and hides why the test is symmetric. A set of the 26 × 26 possible pairs seen so far turns this into a single O(n) pass if the string were long.
Complexity
- Time —
O(n²) with a scan per pair, or O(n) with a set of seen pairs - Space —
O(1), or O(n) with the set
Pitfalls
- A palindromic pair like
aamatches itself — that still counts. - A string of length 1 has no pairs and must return
false. - The match may overlap the original pair; nothing requires them to be disjoint.
Reference solution
Python
def isSubstringPresent(s: str) -> bool:
for i in range(len(s) - 1):
if s[i + 1] + s[i] in s:
return True
return FalseJava
public static boolean isSubstringPresent(String s) {
for (int i = 0; i + 1 < s.length(); i++) {
String pair = "" + s.charAt(i + 1) + s.charAt(i);
if (s.contains(pair)) return true;
}
return false;
}C++
bool isSubstringPresent(string s) {
for (size_t i = 0; i + 1 < s.size(); i++) {
string pair;
pair += s[i + 1];
pair += s[i];
if (s.find(pair) != string::npos) return true;
}
return false;
}JavaScript
var isSubstringPresent = function(s) {
for (var i = 0; i + 1 < s.length; i++) {
var pair = s.charAt(i + 1) + s.charAt(i);
if (s.indexOf(pair) !== -1) return true;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets