Scale Engineer

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

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:
  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.
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;    }}

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.

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 →

Next problem