# 3083. Existence of a Substring in a String and Its Reverse

## Description

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 <= 100
• s consists only of lowercase English letters.

## Solutions

### Solution 1: Hash Table or Array

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$.

• 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))


• func isSubstringPresent(s string) bool {
st := [26][26]bool{}
for i := 0; i < len(s)-1; i++ {
st[s[i+1]-'a'][s[i]-'a'] = true
}
for i := 0; i < len(s)-1; i++ {
if st[s[i]-'a'][s[i+1]-'a'] {
return true
}
}
return false
}

• function isSubstringPresent(s: string): boolean {
const st: boolean[][] = Array.from({ length: 26 }, () => Array(26).fill(false));
for (let i = 0; i < s.length - 1; ++i) {
st[s.charCodeAt(i + 1) - 97][s.charCodeAt(i) - 97] = true;
}
for (let i = 0; i < s.length - 1; ++i) {
if (st[s.charCodeAt(i) - 97][s.charCodeAt(i + 1) - 97]) {
return true;
}
}
return false;
}