Existence of a Substring in a String and Its Reverse

Existence of a Substring in a String and Its Reverse

What is this problem about?

The Existence of a Substring in a String and Its Reverse interview question asks you to determine if there exists any substring of length 2 in a string s that also appears in the reverse of the string. In simpler terms, you need to check if there is a pair of adjacent characters s[i]s[i+1] such that the reversed pair s[i+1]s[i] also exists somewhere in the original string.

Why is this asked in interviews?

Companies like Rubrik use this String interview question as a quick check of your string manipulation and hashing skills. It's an "Easy" difficulty problem that evaluates whether you can efficiently search for patterns. It tests your ability to think about string properties—specifically, that a substring of length 2 in the reverse string is just a reversed pair of adjacent characters in the original string.

Algorithmic pattern used

The problem can be solved using a Hash Set for O(N) efficiency.

1. Create a Hash Set to store all adjacent pairs (length 2 substrings) found in the original string.
2. Iterate through the string from index 0 to n-2.
3. For each pair s[i]s[i+1]:
   • Store it in the set.
   • Check if its reverse s[i+1]s[i] is already in the set.
4. Alternatively, you can just check for every pair s[i]s[i+1] if the string s[i+1]s[i] exists in the original string using a built-in search.

Example explanation

String: s = "abcba"

1. Pair 1: "ab". Reverse: "ba". Does "ba" exist in "abcba"? Yes, at the end.
2. Pair 2: "bc". Reverse: "cb". Does "cb" exist in "abcba"? Yes, in the middle. Result: True.

String: s = "abcd"

1. Pair 1: "ab". Reverse "ba". Not found.
2. Pair 2: "bc". Reverse "cb". Not found. Result: False.

Common mistakes candidates make

• Over-complicating: Reversing the entire string first and then doing a full substring search, which is fine but slightly more work than necessary.
• Off-by-one: Not iterating correctly to the second-to-last character.
• Substring length: Forgetting that the problem specifically asks for length 2 (or checking only one pair).

Interview preparation tip

Whenever a problem involves searching for "any" match, a Hash Set is usually the most efficient tool. It turns a potential O(N^2) search into an O(N) average time complexity.