FastPrepCount Substrings Matching with One Adjacent Swap

Count Substrings Matching with One Adjacent Swap

InMobi logoInMobi● HardNEW GRADOA
Learn

Problem statement

You are given a lowercase text string and a non-empty lowercase pattern. Count text substrings of the pattern's length that either equal the pattern or can be made equal by swapping one pair of adjacent characters in the pattern.

Each starting position contributes at most once, even when equal adjacent characters give multiple equivalent swaps.

Function

countAdjacentSwapMatches(text: String, pattern: String) → int

Examples

Example 1

text = "abcacbabc"pattern = "abc"return = 3

The matching windows are abc, acb, and the final abc.

Example 2

text = "aab"pattern = "ab"return = 1

Only the final window ab matches; aa cannot be obtained by one adjacent swap.

Constraints

  • 1 <= pattern.length <= text.length <= 200000
  • Both strings contain only lowercase English letters.
  • The answer fits in a signed 32-bit integer.

Source note: Interview prompt excerpt preserved as source evidence.

More InMobi problems

See InMobi hiring insights
public int countAdjacentSwapMatches(String text, String pattern) {
    // Write your code here.
}
text"abcacbabc"
pattern"abc"
expected3
Checking account…