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.

Examples

Example 1

Input: s = "abcdefg", pattern = "bcdffg"

Output: 1

Explanation:

The substring `s[1..6] == "bcdefg"` can be converted to `"bcdffg"` by changing
`s[4]` to `"f"`.

Example 2

Input: s = "ababbababa", pattern = "bacaba"

Output: 4

Explanation:

The substring `s[4..9] == "bababa"` can be converted to `"bacaba"` by changing
`s[6]` to `"c"`.

Example 3

Input: s = "abcd", pattern = "dba"

Output: -1

#### Example 4

Input: s = "dde", pattern = "d"

Output: 0

Constraints

• 1 <= pattern.length < s.length <= 10^5
• s and pattern consist only of lowercase English letters.

Follow-up: Could you solve the problem if at most k consecutive characters can be changed?

Solution

Method 1 – Sliding Window with Mismatch Counting

Intuition

We want to find the smallest index where a substring of s is almost equal to pattern, i.e., differs in at most one character. We can use a sliding window of length len(pattern) and count mismatches for each window.

Approach

1. Let m = len(pattern), n = len(s).
2. For each index i from 0 to n - m:
   • Compare s[i:i+m] with pattern character by character.
   • Count the number of mismatches.
   • If mismatches ≤ 1, return i.
3. If no such index is found, return -1.

Code

C++

class Solution {
public:
    int findAlmostEqualSubstring(string s, string pattern) {
        int n = s.size(), m = pattern.size();
        for (int i = 0; i + m <= n; ++i) {
            int diff = 0;
            for (int j = 0; j < m; ++j) {
                if (s[i + j] != pattern[j]) diff++;
                if (diff > 1) break;
            }
            if (diff <= 1) return i;
        }
        return -1;
    }
};

Go

func findAlmostEqualSubstring(s, pattern string) int {
    n, m := len(s), len(pattern)
    for i := 0; i+m <= n; i++ {
        diff := 0
        for j := 0; j < m; j++ {
            if s[i+j] != pattern[j] {
                diff++
                if diff > 1 {
                    break
                }
            }
        }
        if diff <= 1 {
            return i
        }
    }
    return -1
}

Java

class Solution {
    public int findAlmostEqualSubstring(String s, String pattern) {
        int n = s.length(), m = pattern.length();
        for (int i = 0; i + m <= n; ++i) {
            int diff = 0;
            for (int j = 0; j < m; ++j) {
                if (s.charAt(i + j) != pattern.charAt(j)) diff++;
                if (diff > 1) break;
            }
            if (diff <= 1) return i;
        }
        return -1;
    }
}

Kotlin

class Solution {
    fun findAlmostEqualSubstring(s: String, pattern: String): Int {
        val n = s.length
        val m = pattern.length
        for (i in 0..n - m) {
            var diff = 0
            for (j in 0 until m) {
                if (s[i + j] != pattern[j]) diff++
                if (diff > 1) break
            }
            if (diff <= 1) return i
        }
        return -1
    }
}

Python

class Solution:
    def findAlmostEqualSubstring(self, s: str, pattern: str) -> int:
        n, m = len(s), len(pattern)
        for i in range(n - m + 1):
            diff = 0
            for j in range(m):
                if s[i + j] != pattern[j]:
                    diff += 1
                    if diff > 1:
                        break
            if diff <= 1:
                return i
        return -1

Rust

impl Solution {
    pub fn find_almost_equal_substring(s: String, pattern: String) -> i32 {
        let n = s.len();
        let m = pattern.len();
        let s = s.as_bytes();
        let p = pattern.as_bytes();
        for i in 0..=n - m {
            let mut diff = 0;
            for j in 0..m {
                if s[i + j] != p[j] {
                    diff += 1;
                    if diff > 1 {
                        break;
                    }
                }
            }
            if diff <= 1 {
                return i as i32;
            }
        }
        -1
    }
}

TypeScript

class Solution {
    findAlmostEqualSubstring(s: string, pattern: string): number {
        const n = s.length, m = pattern.length;
        for (let i = 0; i + m <= n; ++i) {
            let diff = 0;
            for (let j = 0; j < m; ++j) {
                if (s[i + j] !== pattern[j]) {
                    diff++;
                    if (diff > 1) break;
                }
            }
            if (diff <= 1) return i;
        }
        return -1;
    }
}

Complexity

• ⏰ Time complexity: O(n * m) — For each window, compare up to m characters.
• 🧺 Space complexity: O(1) — Only a few variables for counting and iteration.