Determine equality after limited swaps
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### 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/
Quick Answer: 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.
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
Solution
from collections import deque
def can_make_equal_with_k_adjacent_swaps(s: str, t: str, k: int) -> bool:
n = len(s)
if n != len(t):
return False
# Frequency check (since adjacent swaps cannot change character multiset)
freq = [0] * 26
for ch in s:
freq[ord(ch) - 97] += 1
for ch in t:
freq[ord(ch) - 97] -= 1
for v in freq:
if v != 0:
return False
# Map occurrences: for each char, queue the positions it appears in t
pos_in_t = [deque() for _ in range(26)]
for idx, ch in enumerate(t):
pos_in_t[ord(ch) - 97].append(idx)
# Build the target index sequence corresponding to s's characters
target_indices = [0] * n
for i, ch in enumerate(s):
q = pos_in_t[ord(ch) - 97]
target_indices[i] = q.popleft()
# Count inversions in target_indices using Fenwick Tree
class Fenwick:
def __init__(self, size: int):
self.n = size
self.bit = [0] * (size + 1)
def update(self, i: int, delta: int) -> None:
while i <= self.n:
self.bit[i] += delta
i += i & -i
def query(self, i: int) -> int:
s = 0
while i > 0:
s += self.bit[i]
i -= i & -i
return s
fenwick = Fenwick(n)
inversions = 0
for i, v in enumerate(target_indices):
# Number of prior elements greater than v
inversions += i - fenwick.query(v + 1)
fenwick.update(v + 1, 1)
return inversions <= kExplanation
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).
Hints
- If s and t do not have identical character frequencies, it is impossible.
- 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.
- The minimum number of adjacent swaps equals the inversion count of that permutation.
- Use a Binary Indexed Tree (Fenwick Tree) or a mergesort-based approach to count inversions in O(n log n).