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.
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; }}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.