cswork / libraryOpen practice workspace

Coding questions · DoorDash

Determine equality after limited swaps

This question evaluates string manipulation and combinatorial reasoning about character swaps and anagram formation, focusing on competencies such as frequency analysis and reasoning about minimal edit operations.

Question

LeetCode 1790. Check if One String Swap Can Make Strings Equal Follow-up: Given two strings, determine if they can become anagrams of each other using at most k swaps

https://leetcode.com/problems/check-if-one-string-swap-can-make-strings-equal/description/

Equality with Limited Adjacent Swaps

Given two strings s and t of equal length and a non-negative integer k, you may perform swaps of adjacent characters in s (i.e., swap s[i] and s[i+1]). Determine whether s can be transformed into t using at most k such swaps. If s and t do not have the same multiset of characters, return false.

Constraints

  • 1 <= len(s) = len(t) <= 200000
  • s and t consist only of lowercase English letters ('a'-'z')
  • 0 <= k <= 10^12

Examples

Example 1

Input: s = "aabc", t = "abac", k = 1
Output: true

Explanation: Map each occurrence in s to the same-occurrence index in t: sequence [0,2,1,3] has 1 inversion, so 1 adjacent swap is sufficient.

Example 2

Input: s = "abca", t = "aabc", k = 1
Output: false

Explanation: The sequence [0,2,3,1] has 2 inversions, so at least 2 adjacent swaps are required; k = 1 is insufficient.

Hints

  1. If s and t do not have identical character frequencies, it is impossible.
  2. Match the k-th occurrence of each character in s to the k-th occurrence of the same character in t to form a permutation of target indices.
  3. The minimum number of adjacent swaps equals the inversion count of that permutation.
  4. Use a Binary Indexed Tree (Fenwick Tree) or a mergesort-based approach to count inversions in O(n log n).

Approach

Adjacent swaps do not change character counts, so first ensure s and t are anagrams. To minimize adjacent swaps, match the k-th occurrence of each character in s to the k-th occurrence in t, producing a permutation of target indices. The minimal number of adjacent swaps required equals the inversion count of this permutation. We compute inversions with a Fenwick Tree in O(n log n) time and compare to k.

  • Time complexity: O(n log n)
  • Space complexity: O(n)