Infosys
Online AssessmentLongest Common Substring with At Most 1 Mismatch
You need to find the length of the longest pair of substrings (one from A and one from B) that have the exact same length and differ in at most 1 position.
Additionally, if the two substrings differ in exactly 1 position, the two mismatched characters must either both be vowels ('a', 'e', 'i', 'o', 'u') or both be consonants. If the mismatched characters do not share the same vowel/consonant type, the mismatch is considered invalid and the substrings do not meet the criteria.
Find the length of the longest valid pair of substrings.
- ▸First line: string A.
- ▸Second line: string B.
- ▸Print a single integer representing the length of the longest valid pair of substrings.
- 1 <= |A|, |B| <= 3000
- Strings contain lowercase English letters.
cat bat
3
'c' and 'b' differ in exactly 1 position, and both are consonants. Substrings 'cat' and 'bat' are valid with length 3.
cat cut
3
'a' and 'u' differ in exactly 1 position, and both are vowels. Substrings 'cat' and 'cut' are valid with length 3.
cat eat
2
'c' (consonant) and 'e' (vowel) have different types, making the mismatch invalid. The longest valid matching substring is 'at' with length 2.
1. Any pair of equal-length substrings A[i..i+L-1] and B[j..j+L-1] corresponds to comparing characters along a diagonal d = i - j. 2. Iterate through all diagonals d in [-(|B|-1), |A|-1]: - Along the diagonal, use a two-pointer sliding window [L, R]. - If A[i+R] == B[j+R]: match (0 mismatches). - If mismatched and (isVowel(A[i+R]) == isVowel(B[j+R])): valid mismatch. - If the window already had a mismatch at `mismatchPos`, move L to `mismatchPos + 1`. - Update `mismatchPos = R`. - If mismatched and vowel/consonant types differ: invalid mismatch! The window cannot contain index R, so reset `L = R + 1` and `mismatchPos = -1`. - At each step, update `maxLen = max(maxLen, R - L + 1)`. 3. Time Complexity: O(|A| * |B|), Space Complexity: O(1).