# Find the Occurrence of First Almost Equal Substring
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-occurrence-of-first-almost-equal-substring)
Canonical: https://scaleengineer.com/dsa/problems/find-the-occurrence-of-first-almost-equal-substring
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
---
## 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. 

**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 <= 105`
* `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?

# Approaches
## Brute-Force Approach
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible substring of `s` that has the same length as `pattern`. For each of these substrings, we compare it character by character with `pattern` to count the number of differing characters. If the count is less than or equal to one, we have found a valid substring, and since we are iterating from the beginning, the first one we find will be at the smallest starting index.
**Time:** O(N * M) - Where N is the length of `s` and M is the length of `pattern`. The outer loop runs `N - M + 1` times, and the inner loop runs `M` times. · **Space:** O(1) - We only use a few variables to store lengths and counts, which does not depend on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space, making it very memory efficient.
**Cons:** Highly inefficient for large strings.; Leads to a 'Time Limit Exceeded' (TLE) error on platforms with strict time constraints for the given input sizes.
### Explanation
This method iterates through all possible starting positions for a substring in `s` that matches the length of `pattern`. For each position, it performs a direct character-by-character comparison against `pattern`.

- **Algorithm Steps:**

 1. Get the lengths of `s` and `pattern`, let them be `n` and `m`.
 2. Iterate with an index `i` from `0` to `n - m`. This `i` represents the starting index of a potential substring in `s`.
 3. For each `i`, create a nested loop with index `j` from `0` to `m-1` to compare the substring `s[i...i+m-1]` with `pattern`.
 4. Maintain a `difference_count` for each window, initialized to `0`.
 5. In the inner loop, if `s.charAt(i + j)` is not equal to `pattern.charAt(j)`, increment `difference_count`.
 6. If `difference_count` exceeds `1`, break the inner loop and proceed to the next starting index `i`, as this window is not a valid candidate.
 7. After the inner loop completes, if `difference_count` is `0` or `1`, it means we have found the first almost equal substring. Return the starting index `i`.
 8. If the outer loop finishes without finding any such substring, return `-1`.

```java
class Solution {
    public int firstAlmostEqual(String s, String pattern) {
        int n = s.length();
        int m = pattern.length();

        if (n < m) {
            return -1;
        }

        for (int i = 0; i <= n - m; i++) {
            int diff = 0;
            for (int j = 0; j < m; j++) {
                if (s.charAt(i + j) != pattern.charAt(j)) {
                    diff++;
                    if (diff > 1) {
                        break; // Optimization to exit early
                    }
                }
            }
            if (diff <= 1) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- Get the lengths of `s` and `pattern`, let them be `n` and `m`.
- Iterate with an index `i` from `0` to `n - m`. This `i` represents the starting index of a potential substring in `s`.
- For each `i`, create a nested loop with index `j` from `0` to `m-1` to compare the substring `s[i...i+m-1]` with `pattern`.
- Maintain a `difference_count` for each window, initialized to `0`.
- In the inner loop, if `s.charAt(i + j)` is not equal to `pattern.charAt(j)`, increment `difference_count`.
- If `difference_count` exceeds `1`, break the inner loop and proceed to the next starting index `i`, as this window is not a valid candidate.
- After the inner loop completes, if `difference_count` is `0` or `1`, it means we have found the first almost equal substring. Return the starting index `i`.
- If the outer loop finishes without finding any such substring, return `-1`.

## Rolling Hash with Binary Search
This approach improves upon the brute-force method by using polynomial rolling hash to speed up the comparison process. Instead of comparing characters one by one for each window, we can compare hashes of substrings. To handle the 'at most one difference' condition, we find the length of the longest common prefix (LCP) and longest common suffix (LCS) between the window and the pattern. This can be done efficiently using binary search over the precomputed hash values. If the sum of LCP and LCS lengths is at least `m-1` (where `m` is the pattern length), it implies there's at most one mismatch.
**Time:** O((N - M) * log M) - Precomputation takes O(N + M). The main loop runs N-M times, with each iteration performing two binary searches taking O(log M) time. · **Space:** O(N + M) - To store the precomputed hash arrays for both strings.
**Pros:** Significantly more efficient than the brute-force approach.; Can pass test cases where the brute-force approach would time out.
**Cons:** Implementation is complex, requiring careful handling of hashing, modular arithmetic, and binary search.; Requires extra space proportional to the input string lengths.; There is a theoretical possibility of hash collisions, though it can be minimized by using multiple hash functions or a large prime modulus.
### Explanation
The core idea is to avoid re-computing comparisons for each window from scratch. We use hashing to quickly check for common parts between a substring of `s` and the `pattern`.

- **Algorithm Steps:**

 1. Precompute polynomial rolling hashes for all prefixes of `s` and `pattern`. This allows for O(1) calculation of the hash of any substring.
 2. Similarly, precompute rolling hashes for all suffixes of `s` and `pattern` (by hashing the reversed strings).
 3. Iterate through each possible starting index `i` from `0` to `n - m`.
 4. For each window `s[i:i+m]`, find the length of the Longest Common Prefix (LCP) with `pattern`. This is done using a binary search on the length of the prefix, comparing hashes at each step.
 5. Similarly, find the length of the Longest Common Suffix (LCS) using binary search on the precomputed suffix hashes.
 6. A substring is 'almost equal' if the sum of its LCP and LCS with the pattern is greater than or equal to `m-1`. This condition signifies that there is at most one character mismatch.
 7. If `LCP + LCS >= m - 1`, return the current index `i`.
 8. If the loop completes without finding a match, return -1.

```java
// Note: This is a conceptual snippet. A full implementation requires a robust hashing utility class.
class Solution {
    // Hashing parameters would be defined here (base, modulus)
    // Methods for precomputing hashes and getting substring hashes would be needed.

    public int firstAlmostEqual(String s, String pattern) {
        int n = s.length();
        int m = pattern.length();
        if (n < m) return -1;

        // 1. Precompute forward and backward hashes for s and pattern
        // HashUtil hashUtil = new HashUtil(s, pattern);

        for (int i = 0; i <= n - m; i++) {
            // 2. Find LCP using binary search on forward hashes
            int lcp = findLCP(i, m /*, hashUtil */);

            // 3. Find LCS using binary search on backward hashes
            int lcs = findLCS(i, m /*, hashUtil */);

            // 4. Check condition
            if (lcp + lcs >= m - 1) {
                return i;
            }
        }

        return -1;
    }

    // Helper function for LCP using binary search
    private int findLCP(int sStart, int m /*, HashUtil hashUtil */) {
        int low = 0, high = m, lcp = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                low = mid + 1;
                continue;
            }
            // if (hashUtil.getForwardHashS(sStart, mid) == hashUtil.getForwardHashP(0, mid)) {
            //     lcp = mid;
            //     low = mid + 1;
            // } else {
            //     high = mid - 1;
            // }
        }
        return lcp;
    }

    // Helper function for LCS using binary search
    private int findLCS(int sStart, int m /*, HashUtil hashUtil */) {
        int low = 0, high = m, lcs = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {
                low = mid + 1;
                continue;
            }
            // if (hashUtil.getBackwardHashS(sStart + m - mid, mid) == hashUtil.getBackwardHashP(m - mid, mid)) {
            //     lcs = mid;
            //     low = mid + 1;
            // } else {
            //     high = mid - 1;
            // }
        }
        return lcs;
    }
}
```
### Algorithm
- Precompute polynomial rolling hashes for all prefixes of `s` and `pattern`. This allows for O(1) calculation of the hash of any substring.
- Similarly, precompute rolling hashes for all suffixes of `s` and `pattern` (by hashing the reversed strings).
- Iterate through each possible starting index `i` from `0` to `n - m`.
- For each window `s[i:i+m]`, find the length of the Longest Common Prefix (LCP) with `pattern`. This is done using a binary search on the length of the prefix, comparing hashes at each step.
- Similarly, find the length of the Longest Common Suffix (LCS) using binary search on the precomputed suffix hashes.
- A substring is 'almost equal' if the sum of its LCP and LCS with the pattern is greater than or equal to `m-1`. This condition signifies that there is at most one character mismatch.
- If `LCP + LCS >= m - 1`, return the current index `i`.
- If the loop completes without finding a match, return -1.

## Optimal Approach using Z-Algorithm
This is the most optimal approach, achieving linear time complexity. It uses the Z-algorithm, a powerful string processing tool. The Z-algorithm computes a Z-array, where `Z[i]` is the length of the longest common prefix between the string and its suffix starting at `i`. By applying the Z-algorithm to concatenated strings (`pattern + '#' + s` and `reverse(pattern) + '$' + reverse(s)`), we can precompute the LCP and LCS for all sliding windows in one pass. With these precomputed values, we can check each window in O(1) time.
**Time:** O(N + M) - The Z-algorithm runs in linear time with respect to the string length. We build and process two strings of size roughly N+M. The final loop runs N-M times. · **Space:** O(N + M) - To store the concatenated strings and their corresponding Z-arrays.
**Pros:** Optimal time complexity, making it extremely fast for large inputs.; Provides a deterministic solution without the risk of collisions present in hashing methods.
**Cons:** The Z-algorithm, while efficient, is a non-trivial string algorithm and can be complex to implement correctly from scratch.; Requires significant extra space for the concatenated strings and their Z-arrays.
### Explanation
This approach leverages a classic string algorithm to solve the problem in linear time. The key is to rephrase the problem of finding LCPs and LCSs for all windows as a Z-algorithm problem.

- **Algorithm Steps:**

 1. To find the LCP of `pattern` and every relevant substring of `s`, construct a new string `T_prefix = pattern + '#' + s` (where '#' is a separator not in the alphabets). Compute the Z-array for `T_prefix`. The value `Z[m+1+i]` gives the LCP of `pattern` and `s[i:]`.
 2. To find the LCS, do the same with reversed strings. Construct `T_suffix = reverse(pattern) + '$' + reverse(s)`. Compute its Z-array. The LCS for the window `s[i:i+m]` can be derived from this Z-array.
 3. After O(N+M) precomputation, we have the LCP and LCS values for every possible window.
 4. Iterate from `i = 0` to `n - m`. For each window, check if `lcp[i] + lcs[i] >= m - 1`.
 5. The first index `i` that satisfies this condition is the answer. If the loop finishes, no such substring exists, so return -1.

```java
class Solution {
    public int firstAlmostEqual(String s, String pattern) {
        int n = s.length();
        int m = pattern.length();

        if (n < m) {
            return -1;
        }

        // LCP array calculation
        String tPrefix = pattern + "#" + s;
        int[] zPrefix = calculateZ(tPrefix.toCharArray());

        // LCS array calculation
        String sRev = new StringBuilder(s).reverse().toString();
        String pRev = new StringBuilder(pattern).reverse().toString();
        String tSuffix = pRev + "$" + sRev;
        int[] zSuffix = calculateZ(tSuffix.toCharArray());

        // Check each window
        for (int i = 0; i <= n - m; i++) {
            int lcp = zPrefix[m + 1 + i];
            // LCS for window s[i...i+m-1] corresponds to LCP of pRev and sRev starting at n-i-m
            int lcs = zSuffix[m + 1 + (n - i - m)];

            if (Math.min(m, lcp) + Math.min(m, lcs) >= m - 1) {
                return i;
            }
        }

        return -1;
    }

    // Standard Z-algorithm implementation
    private int[] calculateZ(char[] str) {
        int n = str.length;
        int[] z = new int[n];
        int l = 0, r = 0;
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            while (i + z[i] < n && str[z[i]] == str[i + z[i]]) {
                z[i]++;
            }
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        return z;
    }
}
```
### Algorithm
- To find the LCP of `pattern` and every relevant substring of `s`, construct a new string `T_prefix = pattern + '#' + s` (where '#' is a separator not in the alphabets). Compute the Z-array for `T_prefix`. The value `Z[m+1+i]` gives the LCP of `pattern` and `s[i:]`.
- To find the LCS, do the same with reversed strings. Construct `T_suffix = reverse(pattern) + '$' + reverse(s)`. Compute its Z-array. The LCS for the window `s[i:i+m]` can be derived from this Z-array.
- After O(N+M) precomputation, we have the LCP and LCS values for every possible window.
- Iterate from `i = 0` to `n - m`. For each window, check if `lcp[i] + lcs[i] >= m - 1`.
- The first index `i` that satisfies this condition is the answer. If the loop finishes, no such substring exists, so return -1.