class Solution { public: int minStartingIndex(string s, string pattern) { for (int i=0;…
- User
class Solution { public: int minStartingIndex(string s, string pattern) { for (int i=0; i<=s.length()-pattern.length(); ++i) { int diff=0; for (int j=0; j<pattern.length(); ++j) { if (s[i+j]!=pattern[j]) { diff++; } if (diff>1) { break; } } if (diff<=1) { return i; } } return -1; } };
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.
optimze this for • 1 <= pattern. length < s.length <= 3 * 10^5 • S and pattern consist only of lowercase English letters.
- Assistant
To optimize the given solution for finding the smallest starting index of a substring in
sthat is almost equal topattern(i.e., differs by at most one character), you need to reduce the time complexity from ( O(NP) ) to ( O(N \log N) ), where ( N ) is the length ofsand ( P ) is the length ofpattern.Optimized Approach: Using Fast Fourier Transform (FFT) for Convolution
The idea is to leverage Fast Fourier Transform (FFT) to perform convolution, which allows you to efficiently compute the number of matching characters between
sandpatternacross all possible window positions. Here's a step-by-step explanation:-
Character-Wise Matching:
- For each character
cin the alphabet (a-z), create two binary arrays:- Array A_c: Marks the positions in
swhere the charactercappears. - Array B_c: Marks the positions in
patternwhere the charactercappears. Reverse this array since convolution effectively slidespatternovers.
- Array A_c: Marks the positions in
- For each character
-
Convolution:
- Perform convolution between
A_candB_cfor each characterc. The result of this convolution gives the number of times charactercmatches betweensandpatternat each possible window position.
- Perform convolution between
-
Aggregate Matches:
- Sum the convolution results for all characters. This sum represents the total number of matching characters between
sandpatternfor each window position.
- Sum the convolution results for all characters. This sum represents the total number of matching characters between
-
Determine Mismatches:
- For each window position, calculate the number of mismatches by subtracting the number of matches from the length of the
pattern.
- For each window position, calculate the number of mismatches by subtracting the number of matches from the length of the
-
Find the Minimum Index:
- Identify the smallest index where the number of mismatches is less than or equal to 1.
Implementation Details:
Below is a C++ implementation of the optimized approach using FFT-based convolution. This implementation uses the
std::complexclass for FFT operations and handles the convolution for each character in the alphabet.#include <bits/stdc++.h> using namespace std; typedef complex<double> cd; const double PI = acos(-1); // FFT function void fft(vector<cd> & a, bool invert) { int n = a.size(); // Bit-reversal permutation for(int i = 1, j = 0; i < n; ++i){ int bit = n >> 1; while(j >= bit){ j -= bit; bit >>=1; } if(j < bit) j += bit; if(i < j) swap(a[i], a[j]); } // FFT for(int len = 2; len <= n; len <<=1){ double angle = 2*PI / len * (invert ? -1 : 1); cd wlen(cos(angle), sin(angle)); for(int i=0; i<n; i+=len){ cd w(1); for(int j=0; j<len/2; ++j){ cd u = a[i+j]; cd v = a[i+j+len/2] * w; a[i+j] = u + v; a[i+j+len/2] = u - v; w *= wlen; } } } if(invert){ for(auto & x: a) x /= n; } } // Function to perform convolution vector<long long> multiply(vector<long long> a, vector<long long> b){ int n=1; while(n < a.size() + b.size()) n <<=1; vector<cd> fa(n, 0), fb(n,0); for(int i=0;i<a.size(); ++i) fa[i] = a[i]; for(int i=0;i<b.size(); ++i) fb[i] = b[i]; fft(fa, false); fft(fb, false); for(int i=0;i<n; ++i) fa[i] *= fb[i]; fft(fa, true); vector<long long> result(a.size() + b.size() -1); for(int i=0;i<result.size(); ++i){ result[i] = round(fa[i].real()); } return result; } class Solution { public: int minStartingIndex(string s, string pattern) { int N = s.size(); int P = pattern.size(); if(P > N) return -1; // Initialize a vector to store the total matches vector<long long> total_matches(N + P, 0); // Iterate over each character for(char c = 'a'; c <= 'z'; ++c){ // Prepare binary arrays for s and pattern vector<long long> A; for(char sc : s) A.push_back(sc == c ? 1 : 0); vector<long long> B; for(char pc : pattern) B.push_back(pc == c ? 1 : 0); // Reverse B for convolution reverse(B.begin(), B.end()); // Perform convolution vector<long long> conv = multiply(A, B); // Accumulate the matches for(int i=0; i < conv.size(); ++i){ if(i >= P-1 && i - (P-1) < total_matches.size()){ total_matches[i - (P-1)] += conv[i]; } } } // Now, iterate through each window to find the first with <=1 mismatch for(int i=0; i <= N - P; ++i){ long long matches = total_matches[i]; long long mismatches = P - matches; if(mismatches <=1){ return i; } } return -1; } };Explanation of the Code:
-
FFT Function (
fft):- Implements the Fast Fourier Transform for both forward and inverse transformations.
- The
invertflag determines the direction of the transform.
-
Convolution Function (
multiply):- Pads the input vectors to the next power of two to facilitate FFT.
- Performs FFT on both input arrays, multiplies them point-wise, and then performs an inverse FFT to obtain the convolution result.
-
Main Function (
minStartingIndex):- Iterates over each character in the alphabet.
- For each character, creates binary representations for both
sandpattern. - Reverses the
patternbinary array to align it correctly for convolution. - Performs convolution to find the number of matches for each window.
- Accumulates the matches across all characters.
- Finally, iterates through the accumulated matches to find the smallest index where the number of mismatches is ≤1.
Time and Space Complexity:
- Time Complexity: ( O(26 \cdot N \log N) ) due to performing FFT-based convolution for each of the 26 lowercase English letters.
- Space Complexity: ( O(N) ) for storing intermediate convolution results.
Conclusion:
By leveraging FFT-based convolution, this optimized solution efficiently computes the number of character matches across all possible windows in linearithmic time, making it suitable for large input sizes within the given constraints.
-