We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Occurrence of First Almost Equal Substring

Number: 3580

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given two strings s and pattern, find the smallest starting index of a substring in s that is almost equal to pattern. A string x is called almost equal to y if you can change at most one character in x to transform it into y. If no such substring exists, return -1.

Key Insights

  • The substring in s must have the same length as pattern.
  • Use a sliding window approach to iterate through all possible substrings of s with length equal to pattern.
  • Compare each substring with pattern to count the number of mismatched characters.
  • If the number of mismatches is less than or equal to one, then the substring is almost equal to the pattern.
  • Early exit from the inner loop if mismatches exceed one to optimize performance.
  • The approach ensures we return the smallest starting index that satisfies the condition.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of s and m is the length of pattern. Space Complexity: O(1) extra space (ignoring the input storage).

Solution

The solution iterates over each possible starting index in s where a substring of length equal to pattern can be formed. For each substring, it compares the characters with pattern and counts mismatches. If the mismatch count never exceeds one, the function returns the starting index immediately. If no valid substring is found after checking all possible windows, the function returns -1. For the follow-up question where up to k consecutive characters can be changed, the algorithm would adjust the character comparison logic to allow for up to k consecutive mismatches.

Code Solutions

# Python Code:
def find_almost_equal_substring(s: str, pattern: str) -> int:
    n = len(s)
    m = len(pattern)
    # Check for valid substring length
    if m > n:
        return -1
    # Iterate through each possible starting index
    for i in range(n - m + 1):
        mismatches = 0
        # Compare the substring of s with pattern
        for j in range(m):
            if s[i + j] != pattern[j]:
                mismatches += 1
                # Break early if mismatches exceed one
                if mismatches > 1:
                    break
        # If at most one mismatch, return the current index
        if mismatches <= 1:
            return i
    return -1

# Example usage:
print(find_almost_equal_substring("abcdefg", "bcdffg"))
← Back to All Questions