Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

deepGajera18's blog

String Problem
By deepGajera18, 4 years ago, In English

You are given two strings S and T. you need to find the largest common prefix of two strings S and T if we are allowed to swap two characters in one of the strings?

1 <= |S| <= 100000 1 <= |T| <= 100000

example: S = "abcab" and T = "abbac", then answer would be "abcab". (By swapping characters at index 2 and 4 in string T)

Note: you can perform swap operation at most one time either on string S or string T.

  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Find longest common prefix of $$$S$$$ and $$$T$$$ using KMP. Let's say it's length is $$$X$$$. Now remove this common prefix from both $$$S$$$ and $$$T$$$. So we get our new strings as $$$S'$$$ and $$$T'$$$. Now $$$S'[0] \neq T'[0]$$$ otherwise it will contradict that we have removed longest common prefix.
Part2
Now find the largest index of character $$$T'[0]$$$ in $$$S'[0]$$$. If it does not exist then our final answer will be $$$X$$$ itself. Otherwise let's say it's at index $$$i$$$ in $$$S'$$$. Now swap $$$S'[0]$$$ and $$$S'[i]$$$ in $$$S'$$$. Again find longest common prefix of $$$S'$$$ and $$$T'$$$. Say it's length is $$$Y$$$. Our final answer will be $$$X+Y$$$

Do part2 for $$$T'$$$ also. i.e. find the largest index of character $$$S'[0]$$$ in $$$T'[0]$$$ and do the remaining part. Take maximum of two. Complexity $$$O(N)$$$

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems that we don't need KMP to find the longest common prefix. We can just use brute force.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the input S = "apxx", T = "xpaa". Then, the optimal swap is between indices 0 and 2 in either string, yielding a common prefix "xpa" or "apx" of length 3, while your outline considers only swaps between indices 0 and 3. I leave it as an exercise to modify your approach to correctly account for similar cases.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think we can check all occurrences of T[0] in S, then use precomputed LCP array to calculate new LCP (check LCP between T[1:] and S[1:]. Then if u reach where you swapped from u check that one character and LCP again from S[i+1:] onwards)

      → Reply