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
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).