Existence of a Substring in a String and Its Reverse

Easy
1013.

Existence of a Substring in a String and Its Reverse

Existence of a Substring in a String and Its Reverse is an easy coding problem on strings and hash table, asked in Amazon, Google, Cognizant and Rubrik interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {boolean}
 */
var isSubstringPresent = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Existence of a Substring in a String and Its Reverse Solution

Existence of a Substring in a String and Its Reverse solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Existence of a Substring in a String and Its Reverse is an easy coding problem on strings and hash table, asked in Amazon, Google, Cognizant and Rubrik interviews.

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.

Hints for Existence of a Substring in a String and Its Reverse

  1. Hint 1

    A pair xy appears in the reverse of s exactly when yx appears in s.

  2. Hint 2

    So you never need to build the reversed string at all.

  3. Hint 3

    For every adjacent pair, look for its flip anywhere in s.

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

  1. For each i, form the flipped pair s[i+1] + s[i].
  2. If that pair occurs anywhere in s, return true.
  3. 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

Java

public static boolean isSubstringPresent(String s) {
    for (int i = 0; i + 1 < s.length(); i++) {
        String pair = "" + s.charAt(i + 1) + s.charAt(i);
        if (s.contains(pair)) return true;
    }
    return false;
}

C++

bool isSubstringPresent(string s) {
    for (size_t i = 0; i + 1 < s.size(); i++) {
        string pair;
        pair += s[i + 1];
        pair += s[i];
        if (s.find(pair) != string::npos) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets