Existence of a Substring in a String and Its Reverse

Existence of a Substring in a String and Its Reverse - Problem

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.

Note: A substring is a contiguous sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: s = "abcba"

› Output: true

💡 Note: The 2-character substring "ab" appears at the beginning of the original string and also appears at the beginning of the reversed string "abcba"

Example 2 — No Match

$ Input: s = "abcd"

› Output: false

💡 Note: Original string has substrings "ab", "bc", "cd". Reversed string "dcba" has substrings "dc", "cb", "ba". No common 2-character substring exists.

Example 3 — Single Match

$ Input: s = "leetcode"

› Output: true

💡 Note: The substring "ee" appears in the original string. The reversed string "edocteel" also contains "ee", so return true.

Constraints

1 ≤ s.length ≤ 100
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with all its 2-character substrings

Create Reverse

Generate reversed string and its 2-character substrings

Find Match

Identify any common 2-character substring

Key Takeaway

🎯 Key Insight: Any 2-character substring that appears in both the original string and its reverse indicates the existence of a matching pattern

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we need to find any 2-character substring that appears in both the original string and its reverse. The most efficient approach uses a hash set to store all 2-character substrings from the original string, then checks if any 2-character substring from the reversed string exists in the set. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers from Ends	O(n²)	O(1)	Use two pointers from opposite ends to find matching 2-character patterns
Brute Force - Compare All Pairs	O(n²)	O(1)	Generate all 2-character substrings from original and reversed string, compare each pair
Hash Set Optimization	O(n)	O(n)	Store all 2-character substrings from original string in a set, then check reversed string substrings

Two Pointers from Ends — Algorithm Steps

Step 1: Initialize left pointer at start, right pointer at end
Step 2: Extract 2-char substring from left position and corresponding reverse position
Step 3: Compare patterns and move pointers inward until match found or pointers meet

Visualization

Tap to expand

Step-by-Step Walkthrough

Set Pointers

Left pointer at start, right pointer at end

Extract & Reverse

Get 2-char substring from left, get and reverse 2-char from right position

Compare

Check if substrings match, move pointers if needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int len = strlen(s);
    if (len < 2) {
        return 0;
    }
    
    // Check all 2-char substrings from original string
    for (int i = 0; i < len - 1; i++) {
        char originalSubstr[3] = {s[i], s[i+1], '\0'};
        
        // Check if this substring appears in the reverse direction
        for (int j = 0; j < len - 1; j++) {
            int reverseIdx = len - 2 - j;
            if (reverseIdx >= 0 && reverseIdx < len - 1) {
                char reverseSubstr[3] = {s[reverseIdx+1], s[reverseIdx], '\0'};
                if (strcmp(originalSubstr, reverseSubstr) == 0) {
                    return 1;
                }
            }
        }
    }
    
    return 0;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    
    int result = solution(s);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position of left pointer, we may need to check all possible right positions, leading to nested iteration

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for pointers and substring comparison

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers from Ends — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler