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 <= 100s consists only of lowercase English letters.Problem Overview: Given a string s, determine whether there exists a substring of length two such that its reverse also appears somewhere in the string. For example, if "ab" exists and "ba" also exists, the answer is true. The task is essentially detecting mirrored two‑character patterns inside the same string.
Approach 1: Using Sorting (O(n log n) time, O(n) space)
Generate all substrings of length two by iterating through the string once. Store each pair in an array, and also generate their reversed forms. Sorting both collections allows you to efficiently compare them and detect whether any pair matches its reversed counterpart. After sorting, you can scan with two pointers or binary search to find intersections between the substring list and reversed substring list.
This approach relies on ordering rather than constant-time lookups. The key idea is that once substrings are sorted, equal strings become adjacent, making matches easy to detect. Time complexity becomes O(n log n) due to sorting, and the auxiliary storage for substrings requires O(n) space. While not optimal, it demonstrates a straightforward transformation of a string problem into a searchable dataset.
Approach 2: Using Hashing (O(n) time, O(n) space)
Iterate through the string and extract every substring of length two. Insert each substring into a hash set. For every pair s[i]s[i+1], compute its reverse s[i+1]s[i] and check if it already exists in the set. A constant-time hash lookup immediately tells you whether the reversed pattern has appeared earlier.
The insight is that the substring length is fixed at two. That allows fast generation and constant-time membership checks with a hash table. Each step performs simple operations: substring creation, reversal, and hash lookup. The entire scan runs in linear time O(n) with O(n) space for storing seen substrings.
This method is the standard solution used in most editorial explanations. It avoids sorting overhead and uses direct lookups, which is ideal for short substring matching problems commonly seen in string and hash-table interview questions.
Recommended for interviews: The hashing approach. It shows you recognize fixed-length substring patterns and can reduce the problem to constant-time lookups. Mentioning the sorting method can demonstrate baseline reasoning, but interviewers expect the O(n) hash-set solution because it minimizes both logic complexity and runtime.
This approach involves sorting the array first, then using a two-pointer technique to solve the problem. By sorting, we can utilize the sorted order to efficiently find pairs or triplets that meet our requirements.
This C code uses the qsort function to sort the array. A pointer approach is then used to find a pair that sums to the target. It iterates from both ends towards the center.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we're sorting in place.
In this approach, a hash map (or dictionary) is used to keep track of the elements we have seen so far and their respective indices. This allows for efficient look-up to find pairs that sum to the target value without needing to sort the array.
This C code creates a basic hash table using an array of pointers to store key-value pairs. The target complement is computed for each element, and we check if it has been previously added, ensuring a quick lookup.
Time Complexity: O(n) on average due to hash map operations.
Space Complexity: O(n) as we need to store entries in the hash table.
We can use a hash table or a two-dimensional array st to store all substrings of length 2 of the reversed string s.
Then we traverse the string s. For each substring of length 2, we check whether it has appeared in st. If it has, we return true. Otherwise, we return false after the traversal.
The time complexity is O(n) and the space complexity is O(|\Sigma|^2). Here, n is the length of the string s, and \Sigma is the character set of the string s. In this problem, \Sigma consists of lowercase English letters, so |\Sigma| = 26.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Sorting | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Using Hashing | Time Complexity: O(n) on average due to hash map operations. |
| Hash Table or Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting substrings | O(n log n) | O(n) | When converting substring comparisons into sorted datasets or when practicing sorting-based matching techniques |
| Hash set lookup | O(n) | O(n) | General case and interview settings where constant-time substring lookup is preferred |
Leetcode | 3083. Existence of a Substring in a String and Its Reverse | Easy | Java Solution • Developer Docs • 604 views views
Watch 8 more video solutions →Practice Existence of a Substring in a String and Its Reverse with our built-in code editor and test cases.
Practice on FleetCode