Existence of a Substring in a String and Its Reverse
EasyPrompt
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 <= 100sconsists only of lowercase English letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It first computes the reverse of the input string s. Then, it iterates through all possible substrings of length 2 from the original string s. For each of these substrings, it checks if the substring exists within the reversed string. If a match is found, it immediately returns true. If the loop completes without finding any such substring, it means none exist, and the function returns false.
Algorithm
- Create a new string
reversedSby reversing the input strings. - Loop with an index
ifrom0tos.length() - 2. - In each iteration, extract the substring of length 2 starting at
i, let's call itsub.sub = s.substring(i, i + 2). - Check if
reversedScontainssubusing the built-incontainsmethod. - If it does, a valid substring has been found. Return
true. - If the loop finishes without returning, it means no such substring was found. Return
false.
Walkthrough
The core idea is to have both the original string and its reverse available. We generate all length-2 substrings from the original string one by one and perform a search for each of them in the reversed string. The first one we find satisfies the condition, and we can stop. While simple, the repeated searching within the reversed string for each substring makes this approach computationally expensive.
class Solution { public boolean isSubstringPresent(String s) { StringBuilder sb = new StringBuilder(s); String reversedS = sb.reverse().toString(); for (int i = 0; i < s.length() - 1; i++) { String sub = s.substring(i, i + 2); if (reversedS.contains(sub)) { return true; } } return false; }}Complexity
Time
O(N^2), where N is the length of the string. Reversing the string takes `O(N)`. The main loop runs `N-1` times. Inside the loop, `substring()` takes constant time (for length 2), but `String.contains()` takes `O(N)` time in the worst case. This leads to a total time complexity of `O(N) + (N-1)*O(N)`, which simplifies to `O(N^2)`.
Space
O(N), where N is the length of the string `s`. This space is required to store the reversed string.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem description.
Cons
Inefficient time complexity, making it slow for large strings.
Uses extra space proportional to the string length.
This approach is based on a key insight: a substring sub exists in reverse(s) if and only if reverse(sub) exists in s. Therefore, the problem reduces to finding if any length-2 substring s[i:i+2] has its reverse, s[i+1]s[i], also present as a substring somewhere in s. This can be checked using nested loops. The outer loop picks a substring, and the inner loop searches for its reverse. This avoids the need to create the entire reversed string, saving space compared to the first approach.
Algorithm
- Loop with an index
ifrom0tos.length() - 2to select the first character of a potential substring froms. - This substring is
s[i:i+2]. - Its reverse is formed by the characters
s[i+1]ands[i]. - Loop with an index
jfrom0tos.length() - 2to search for this reversed substring withins. - Check if
s.charAt(j) == s.charAt(i + 1)ands.charAt(j + 1) == s.charAt(i). - If the condition is met, it means the substring at
jis the reverse of the substring ati. Returntrue. - If the loops complete without finding a match, return
false.
Walkthrough
By using this logical equivalence, we eliminate the need for an explicit O(N) space to store the reversed string. We iterate through each possible length-2 substring with an outer loop. For each such substring, we use an inner loop to scan the entire string again, looking for a substring that is its exact reverse. This trades the space for time, resulting in a space-efficient but time-intensive solution.
class Solution { public boolean isSubstringPresent(String s) { int n = s.length(); if (n < 2) { return false; } for (int i = 0; i < n - 1; i++) { char c1 = s.charAt(i); char c2 = s.charAt(i + 1); // Now search for the reversed substring "c2c1" for (int j = 0; j < n - 1; j++) { if (s.charAt(j) == c2 && s.charAt(j + 1) == c1) { return true; } } } return false; }}Complexity
Time
O(N^2), where N is the length of the string. The two nested loops each run up to `N-1` times, leading to a quadratic time complexity.
Space
O(1), as we are only using a few variables to store characters and indices, not creating any new data structures that scale with the input size.
Trade-offs
Pros
Very space-efficient, using constant extra space.
Avoids creating a new reversed string object.
Cons
The time complexity is quadratic, which is inefficient for large inputs.
This is the most efficient approach in terms of time complexity. It also leverages the property that we are looking for a substring sub whose reverse rev(sub) is also a substring of s. To avoid the O(N) search time of the previous approaches, we use a HashSet to store the substrings we've seen. A HashSet provides average O(1) time complexity for insertions and lookups. By iterating through the string just once, we can check for the existence of the reversed pair in near-constant time, leading to an overall linear time solution.
Algorithm
- Create a
HashSetto store representations of 2-character substrings encountered so far. - Iterate through the string
sfromi = 0tos.length() - 2. - For each
i, get the current substringsub = s.substring(i, i + 2). - Also, form its reverse,
revSub. - Check if
revSubis already present in theHashSet. If yes, a match is found, returntrue. - Also, check if
subis a palindrome (i.e.,sub.equals(revSub)). If it is, a match is found, returntrue. - Add the current
subto theHashSetto be checked against in future iterations. - If the loop completes, no match was found, so return
false.
Walkthrough
We process the string from left to right. For each length-2 substring, we check two conditions: 1) Is its reverse already in our set of seen substrings? This handles cases like "ab...ba". 2) Is the substring itself a palindrome (like "ee")? If a palindromic substring exists, it is present in s, and its reverse (which is itself) is also present in s, satisfying the condition. If either check passes, we return true. Otherwise, we add the current substring to the set and continue. This single pass is sufficient to find any such pair.
import java.util.HashSet;import java.util.Set; class Solution { public boolean isSubstringPresent(String s) { if (s.length() < 2) { return false; } Set<String> seen = new HashSet<>(); for (int i = 0; i < s.length() - 1; i++) { String sub = s.substring(i, i + 2); String revSub = new StringBuilder(sub).reverse().toString(); if (sub.equals(revSub)) { return true; // Palindromic substring found } if (seen.contains(revSub)) { return true; // Found a substring whose reverse appeared earlier } seen.add(sub); } return false; }}Complexity
Time
O(N), where N is the length of the string. We iterate through the string once. Inside the loop, substring creation, reversal, and HashSet operations (add, contains) take constant time on average because the substring length is fixed at 2.
Space
O(K), where K is the number of unique substrings of length 2. Since the alphabet is lowercase English letters, K is at most 26*26 = 676. Thus, the space is constant, O(1). If the alphabet were unbounded, it would be O(N).
Trade-offs
Pros
Optimal time complexity of O(N).
Conceptually clean, trading space for a significant gain in time.
Cons
Uses extra space for the HashSet. For very large alphabets and strings, this could be significant, but for this problem's constraints, it's minimal.
Solutions
Solution
class Solution {public boolean isSubstringPresent(String s) { boolean[][] st = new boolean[26][26]; int n = s.length(); for (int i = 0; i < n - 1; ++i) { st[s.charAt(i + 1) - 'a'][s.charAt(i) - 'a'] = true; } for (int i = 0; i < n - 1; ++i) { if (st[s.charAt(i) - 'a'][s.charAt(i + 1) - 'a']) { return true; } } return false; }}class Solution {public: bool isSubstringPresent(string s) { bool st[26][26]{}; int n = s.size(); for (int i = 0; i < n - 1; ++i) { st[s[i + 1] - 'a'][s[i] - 'a'] = true; } for (int i = 0; i < n - 1; ++i) { if (st[s[i] - 'a'][s[i + 1] - 'a']) { return true; } } return false; }};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))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.