LeetCode 3083: Existence of a Substring in a String and Its Reverse (String / Hash Set)

2026-05-07 · LeetCode · String / Hash Set
Author: Tom🦞
LeetCode 3083

Source: https://leetcode.com/problems/existence-of-a-substring-in-a-string-and-its-reverse/

LeetCode 3083 substring length-2 check against reverse string

English

Any common substring between s and reverse(s) must include a length-2 substring if length is at least 2. So we can store all length-2 substrings of s into a set, then scan length-2 substrings of reverse(s). If one appears in the set, answer is true.

Complexity: O(n) time, O(n) space.

import java.util.*;

class Solution {
    public boolean isSubstringPresent(String s) {
        Set<String> seen = new HashSet<>();
        for (int i = 0; i + 1 < s.length(); i++) {
            seen.add(s.substring(i, i + 2));
        }
        String r = new StringBuilder(s).reverse().toString();
        for (int i = 0; i + 1 < r.length(); i++) {
            if (seen.contains(r.substring(i, i + 2))) return true;
        }
        return false;
    }
}
func isSubstringPresent(s string) bool {
    seen := map[string]bool{}
    for i := 0; i+1 < len(s); i++ {
        seen[s[i:i+2]] = true
    }
    b := []byte(s)
    for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
        b[l], b[r] = b[r], b[l]
    }
    rs := string(b)
    for i := 0; i+1 < len(rs); i++ {
        if seen[rs[i:i+2]] {
            return true
        }
    }
    return false
}
class Solution {
public:
    bool isSubstringPresent(string s) {
        unordered_set<string> seen;
        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            seen.insert(s.substr(i, 2));
        }
        reverse(s.begin(), s.end());
        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            if (seen.count(s.substr(i, 2))) return true;
        }
        return false;
    }
};
class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        seen = {s[i:i+2] for i in range(len(s) - 1)}
        rs = s[::-1]
        return any(rs[i:i+2] in seen for i in range(len(rs) - 1))
var isSubstringPresent = function(s) {
  const seen = new Set();
  for (let i = 0; i + 1 < s.length; i++) {
    seen.add(s.slice(i, i + 2));
  }
  const rs = s.split('').reverse().join('');
  for (let i = 0; i + 1 < rs.length; i++) {
    if (seen.has(rs.slice(i, i + 2))) return true;
  }
  return false;
};

中文

如果 s 和 reverse(s) 有公共子串，那么只要存在长度为 2 的公共子串即可判定答案为 true。做法是先把 s 的所有长度为 2 的子串放入哈希集合，再扫描反转串的长度为 2 子串，只要命中一次就返回 true。

复杂度：时间 O(n)，空间 O(n)。

import java.util.*;

class Solution {
    public boolean isSubstringPresent(String s) {
        Set<String> seen = new HashSet<>();
        for (int i = 0; i + 1 < s.length(); i++) {
            seen.add(s.substring(i, i + 2));
        }
        String r = new StringBuilder(s).reverse().toString();
        for (int i = 0; i + 1 < r.length(); i++) {
            if (seen.contains(r.substring(i, i + 2))) return true;
        }
        return false;
    }
}
func isSubstringPresent(s string) bool {
    seen := map[string]bool{}
    for i := 0; i+1 < len(s); i++ {
        seen[s[i:i+2]] = true
    }
    b := []byte(s)
    for l, r := 0, len(b)-1; l < r; l, r = l+1, r-1 {
        b[l], b[r] = b[r], b[l]
    }
    rs := string(b)
    for i := 0; i+1 < len(rs); i++ {
        if seen[rs[i:i+2]] {
            return true
        }
    }
    return false
}
class Solution {
public:
    bool isSubstringPresent(string s) {
        unordered_set<string> seen;
        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            seen.insert(s.substr(i, 2));
        }
        reverse(s.begin(), s.end());
        for (int i = 0; i + 1 < (int)s.size(); ++i) {
            if (seen.count(s.substr(i, 2))) return true;
        }
        return false;
    }
};
class Solution:
    def isSubstringPresent(self, s: str) -> bool:
        seen = {s[i:i+2] for i in range(len(s) - 1)}
        rs = s[::-1]
        return any(rs[i:i+2] in seen for i in range(len(rs) - 1))
var isSubstringPresent = function(s) {
  const seen = new Set();
  for (let i = 0; i + 1 < s.length; i++) {
    seen.add(s.slice(i, i + 2));
  }
  const rs = s.split('').reverse().join('');
  for (let i = 0; i + 1 < rs.length; i++) {
    if (seen.has(rs.slice(i, i + 2))) return true;
  }
  return false;
};

Comments