Existence of a Substring in a String and Its Reverse - Video Solutions

Problem Overview: Given a string s, determine whether there exists a substring of length two such that its reverse also appears somewhere in the string. For example, if "ab" exists and "ba" also exists, the answer is true. The task is essentially detecting mirrored two‑character patterns inside the same string.

Approach 1: Using Sorting (O(n log n) time, O(n) space)

Generate all substrings of length two by iterating through the string once. Store each pair in an array, and also generate their reversed forms. Sorting both collections allows you to efficiently compare them and detect whether any pair matches its reversed counterpart. After sorting, you can scan with two pointers or binary search to find intersections between the substring list and reversed substring list.

This approach relies on ordering rather than constant-time lookups. The key idea is that once substrings are sorted, equal strings become adjacent, making matches easy to detect. Time complexity becomes O(n log n) due to sorting, and the auxiliary storage for substrings requires O(n) space. While not optimal, it demonstrates a straightforward transformation of a string problem into a searchable dataset.

Approach 2: Using Hashing (O(n) time, O(n) space)

Iterate through the string and extract every substring of length two. Insert each substring into a hash set. For every pair s[i]s[i+1], compute its reverse s[i+1]s[i] and check if it already exists in the set. A constant-time hash lookup immediately tells you whether the reversed pattern has appeared earlier.

The insight is that the substring length is fixed at two. That allows fast generation and constant-time membership checks with a hash table. Each step performs simple operations: substring creation, reversal, and hash lookup. The entire scan runs in linear time O(n) with O(n) space for storing seen substrings.

This method is the standard solution used in most editorial explanations. It avoids sorting overhead and uses direct lookups, which is ideal for short substring matching problems commonly seen in string and hash-table interview questions.

Recommended for interviews: The hashing approach. It shows you recognize fixed-length substring patterns and can reduce the problem to constant-time lookups. Mentioning the sorting method can demonstrate baseline reasoning, but interviewers expect the O(n) hash-set solution because it minimizes both logic complexity and runtime.