Existence of a Substring in a String and Its Reverse — Easy Problem & Solution

Return true if any substring of s of length 2 also occurs in the reverse of s, and false otherwise.

Difficulty: Easy
Topics: Strings, Hash Table
Asked at: Amazon, Google, Cognizant
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return true if any substring of s of length 2 also occurs in the reverse of s, and false otherwise.

Example 1

Input: s = "reedkairo"
Output: true
Explanation: `ee` occurs in the reverse `oriakdeer`.

Example 2

Input: s = "codekairo"
Output: false
Explanation: None of `co`, `od`, `de`, `ek`, `ka`, `ai`, `ir`, `ro` survives the reversal.

Example 3

Input: s = "abcba"
Output: true
Explanation: `bc` occurs in the reverse, which is the same string.

Constraints

1 <= s.length <= 100
s consists only of lowercase English letters.

How to solve Existence of a Substring in a String and Its Reverse

Reversing s maps a substring xy to yx, so xy occurs in the reverse precisely when yx occurs in s. Check each adjacent pair's flip against the original string.

Approach

For each i, form the flipped pair s[i+1] + s[i].
If that pair occurs anywhere in s, return true.
Return false if none does.

Why it works

The flip identity is what removes the reversal entirely — building the reversed string and searching it would work but doubles the memory and hides why the test is symmetric. A set of the 26 × 26 possible pairs seen so far turns this into a single O(n) pass if the string were long.

Complexity

Time — O(n²) with a scan per pair, or O(n) with a set of seen pairs
Space — O(1), or O(n) with the set

Pitfalls

A palindromic pair like aa matches itself — that still counts.
A string of length 1 has no pairs and must return false.
The match may overlap the original pair; nothing requires them to be disjoint.

Reference solution

Python

def isSubstringPresent(s: str) -> bool:
    for i in range(len(s) - 1):
        if s[i + 1] + s[i] in s:
            return True
    return False

JavaScript

var isSubstringPresent = function(s) {
    for (var i = 0; i + 1 < s.length; i++) {
        var pair = s.charAt(i + 1) + s.charAt(i);
        if (s.indexOf(pair) !== -1) return true;
    }
    return false;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue