Problem

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, andfalse otherwise.

Examples

Example 1

1
2
3
4
5
6
7


Input: s = "leetcode"

Output: true

Explanation: Substring `"ee"` is of length `2` which is also present in
`reverse(s) == "edocteel"`.

Example 2

1
2
3
4
5
6
7


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

1
2
3
4
5
6
7


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.

Solution

Method 1 – Hash Set for Substrings

Intuition

If any substring of length 2 in s is also present in the reverse of s, then there is an overlap. We can collect all substrings of length 2 from s and from reverse(s), and check for intersection.

Approach

  1. If the length of s is less than 2, return false.
  2. Collect all substrings of length 2 from s into a set.
  3. Reverse s and collect all substrings of length 2 from the reversed string into another set.
  4. Check if there is any intersection between the two sets.
  5. Return true if there is an intersection, otherwise false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    bool hasSubstringInReverse(string s) {
        if (s.size() < 2) return false;
        unordered_set<string> subs, revsubs;
        for (int i = 0; i + 1 < s.size(); ++i) subs.insert(s.substr(i, 2));
        reverse(s.begin(), s.end());
        for (int i = 0; i + 1 < s.size(); ++i) revsubs.insert(s.substr(i, 2));
        for (auto& sub : subs) if (revsubs.count(sub)) return true;
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public boolean hasSubstringInReverse(String s) {
        if (s.length() < 2) return false;
        Set<String> subs = new HashSet<>();
        Set<String> revsubs = new HashSet<>();
        for (int i = 0; i + 1 < s.length(); ++i) subs.add(s.substring(i, i+2));
        StringBuilder sb = new StringBuilder(s).reverse();
        for (int i = 0; i + 1 < s.length(); ++i) revsubs.add(sb.substring(i, i+2));
        for (String sub : subs) if (revsubs.contains(sub)) return true;
        return false;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def hasSubstringInReverse(self, s: str) -> bool:
        if len(s) < 2:
            return False
        subs = set(s[i:i+2] for i in range(len(s)-1))
        rev = s[::-1]
        revsubs = set(rev[i:i+2] for i in range(len(rev)-1))
        return not subs.isdisjoint(revsubs)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

use std::collections::HashSet;
impl Solution {
    pub fn has_substring_in_reverse(s: String) -> bool {
        if s.len() < 2 { return false; }
        let subs: HashSet<_> = s.as_bytes().windows(2).map(|w| w.to_vec()).collect();
        let rev: Vec<u8> = s.bytes().rev().collect();
        let revsubs: HashSet<_> = rev.windows(2).map(|w| w.to_vec()).collect();
        subs.intersection(&revsubs).next().is_some()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    hasSubstringInReverse(s: string): boolean {
        if (s.length < 2) return false;
        const subs = new Set<string>();
        for (let i = 0; i + 1 < s.length; ++i) subs.add(s.substring(i, i+2));
        const rev = s.split('').reverse().join('');
        const revsubs = new Set<string>();
        for (let i = 0; i + 1 < rev.length; ++i) revsubs.add(rev.substring(i, i+2));
        for (const sub of subs) if (revsubs.has(sub)) return true;
        return false;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s (since substring extraction and set operations are linear).
  • 🧺 Space complexity: O(n), for storing the sets of substrings.