Find the Occurrence of First Almost Equal Substring

Hard

#2933Time: 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.

Patterns

String Matching

Data structures

String

Prompt

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 <= 10⁵
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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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.

1class Solution {2    public int firstAlmostEqual(String s, String pattern) {3        int n = s.length();4        int m = pattern.length();5 6        if (n < m) {7            return -1;8        }9 10        for (int i = 0; i <= n - m; i++) {11            int diff = 0;12            for (int j = 0; j < m; j++) {13                if (s.charAt(i + j) != pattern.charAt(j)) {14                    diff++;15                    if (diff > 1) {16                        break; // Optimization to exit early17                    }18                }19            }20            if (diff <= 1) {21                return i;22            }23        }24 25        return -1;26    }27}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

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.

1// Note: This is a conceptual snippet. A full implementation requires a robust hashing utility class.2class Solution {3    // Hashing parameters would be defined here (base, modulus)4    // Methods for precomputing hashes and getting substring hashes would be needed.5 6    public int firstAlmostEqual(String s, String pattern) {7        int n = s.length();8        int m = pattern.length();9        if (n < m) return -1;10 11        // 1. Precompute forward and backward hashes for s and pattern12        // HashUtil hashUtil = new HashUtil(s, pattern);13 14        for (int i = 0; i <= n - m; i++) {15            // 2. Find LCP using binary search on forward hashes16            int lcp = findLCP(i, m /*, hashUtil */);17 18            // 3. Find LCS using binary search on backward hashes19            int lcs = findLCS(i, m /*, hashUtil */);20 21            // 4. Check condition22            if (lcp + lcs >= m - 1) {23                return i;24            }25        }26 27        return -1;28    }29 30    // Helper function for LCP using binary search31    private int findLCP(int sStart, int m /*, HashUtil hashUtil */) {32        int low = 0, high = m, lcp = 0;33        while (low <= high) {34            int mid = low + (high - low) / 2;35            if (mid == 0) {36                low = mid + 1;37                continue;38            }39            // if (hashUtil.getForwardHashS(sStart, mid) == hashUtil.getForwardHashP(0, mid)) {40            //     lcp = mid;41            //     low = mid + 1;42            // } else {43            //     high = mid - 1;44            // }45        }46        return lcp;47    }48 49    // Helper function for LCS using binary search50    private int findLCS(int sStart, int m /*, HashUtil hashUtil */) {51        int low = 0, high = m, lcs = 0;52        while (low <= high) {53            int mid = low + (high - low) / 2;54            if (mid == 0) {55                low = mid + 1;56                continue;57            }58            // if (hashUtil.getBackwardHashS(sStart + m - mid, mid) == hashUtil.getBackwardHashP(m - mid, mid)) {59            //     lcs = mid;60            //     low = mid + 1;61            // } else {62            //     high = mid - 1;63            // }64        }65        return lcs;66    }67}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

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.

1class Solution {2    public int firstAlmostEqual(String s, String pattern) {3        int n = s.length();4        int m = pattern.length();5 6        if (n < m) {7            return -1;8        }9 10        // LCP array calculation11        String tPrefix = pattern + "#" + s;12        int[] zPrefix = calculateZ(tPrefix.toCharArray());13 14        // LCS array calculation15        String sRev = new StringBuilder(s).reverse().toString();16        String pRev = new StringBuilder(pattern).reverse().toString();17        String tSuffix = pRev + "$" + sRev;18        int[] zSuffix = calculateZ(tSuffix.toCharArray());19 20        // Check each window21        for (int i = 0; i <= n - m; i++) {22            int lcp = zPrefix[m + 1 + i];23            // LCS for window s[i...i+m-1] corresponds to LCP of pRev and sRev starting at n-i-m24            int lcs = zSuffix[m + 1 + (n - i - m)];25 26            if (Math.min(m, lcp) + Math.min(m, lcs) >= m - 1) {27                return i;28            }29        }30 31        return -1;32    }33 34    // Standard Z-algorithm implementation35    private int[] calculateZ(char[] str) {36        int n = str.length;37        int[] z = new int[n];38        int l = 0, r = 0;39        for (int i = 1; i < n; i++) {40            if (i <= r) {41                z[i] = Math.min(r - i + 1, z[i - l]);42            }43            while (i + z[i] < n && str[z[i]] == str[i + z[i]]) {44                z[i]++;45            }46            if (i + z[i] - 1 > r) {47                l = i;48                r = i + z[i] - 1;49            }50        }51        return z;52    }53}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem