Find the Occurrence of First Almost Equal Substring

Find the Occurrence of First Almost Equal Substring - Problem

You are given two strings s and pattern.

A string x is called almost equal to y if you can change at most one character in x to make it identical to y.

Return the smallest starting index of a substring in s that is almost equal to pattern. If no such index exists, return -1.

A substring is a contiguous non-empty sequence of characters within a string.

Input & Output

Example 1 — Basic Almost Equal

$ Input: s = "leetcode", pattern = "leotcode"

› Output: 0

💡 Note: The substring "leetcode" starting at index 0 differs from "leotcode" by only 1 character (e vs o at position 2), so it's almost equal.

Example 2 — No Match Found

$ Input: s = "abcdef", pattern = "xyz"

› Output: -1

💡 Note: No substring of length 3 in "abcdef" is almost equal to "xyz" (all would have 3 mismatches).

Example 3 — Exact Match

$ Input: s = "hello", pattern = "ell"

› Output: 1

💡 Note: The substring "ell" starting at index 1 is exactly equal to pattern "ell" (0 differences ≤ 1).

Constraints

1 ≤ s.length, pattern.length ≤ 10⁵
s and pattern consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s and pattern to match

Process

Check each substring and count differences

Output

Return index of first almost equal substring

Key Takeaway

🎯 Key Insight: Count character differences - if ≤1, the substring is almost equal

Asked in

G Google 15 M Meta 12 M Microsoft 8

The key insight is that we need to find substrings with at most 1 character difference. The best approach uses brute force with early termination - check each position and count mismatches, stopping early when count exceeds 1. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Position	O(n×m)	O(1)	Check each possible starting position and count character differences
Early Termination Optimization	O(n×m)	O(1)	Same approach but with early termination when mismatches exceed 1

Brute Force - Check Every Position — Algorithm Steps

Step 1: Iterate through each valid starting position in s
Step 2: For each position, compare substring with pattern character by character
Step 3: Count mismatches - if ≤ 1, return current index
Step 4: If no valid substring found, return -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Position 0

Compare substring with pattern

Count Mismatches

Stop early if >1 difference

Return First Valid

Return index when ≤1 mismatch found

Code -

solution.c — C

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

int solution(char* s, char* pattern) {
    int n = strlen(s), m = strlen(pattern);
    
    for (int i = 0; i <= n - m; i++) {
        int differences = 0;
        for (int j = 0; j < m; j++) {
            if (s[i + j] != pattern[j]) {
                differences++;
                if (differences > 1) break;
            }
        }
        
        if (differences <= 1) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char s[100001], pattern[100001];
    fgets(s, sizeof(s), stdin);
    fgets(pattern, sizeof(pattern), stdin);
    
    // Remove newlines
    s[strcspn(s, "\n")] = 0;
    pattern[strcspn(pattern, "\n")] = 0;
    
    int result = solution(s, pattern);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Outer loop runs n-m+1 times, inner comparison takes m characters

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

450 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

Brute Force - Check Every Position — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler