Katkat
Back

Solve four OA algorithm problems

TikTokSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize string manipulation using greedy approaches and Fenwick trees to count minimum adjacent swaps required to transform a string into a palindrome.

Problem: Minimum Swaps to Palindrome

Given a string s, you are tasked to determine the minimum number of adjacent swaps required to make the string a palindrome. If it is impossible to form a palindrome, return -1.

Constraints

  • The length of the string n is between 1 and 2,000.
  • The string consists of lowercase English letters.

Implementation

Implement the function min_swaps_to_palindrome(s: str) -> int.

Examples

Example 1: Input: s = "aabb" Output: 2 Explanation: "aabb" -> "abab" -> "abba".

Example 2: Input: s = "ntiin" Output: 1 Explanation: "ntiin" -> "nitin".

Edge Cases

  • String with an odd length that already requires one character to be moved to the center.
  • Strings where a palindrome is impossible (e.g., more than one character has an odd frequency).

Notes

  • Use a greedy strategy: identify the matching pair for the leftmost character, move the rightmost match to the current required position, and count the swaps.

Hints

Hint 1

First, verify if a palindrome can be formed by counting the frequencies of each character; at most one character can have an odd frequency.

Hint 2

Use a two-pointer approach where the left pointer `i` moves from `0` to `n/2` and the right pointer `j` searches for the character matching `s[i]` starting from the end of the string.

Hint 3

If no match is found for `s[i]`, the character must be the 'odd' one; move it to the middle of the string and add the distance to your swap count.

Follow-up questions

  • How does the time complexity change if we use a Fenwick tree (Binary Indexed Tree) to track the relative positions of characters after swaps?
  • What modifications are needed if the constraint on `n` increases to 10^5?
  • If we are allowed to perform non-adjacent swaps instead of adjacent swaps, how does the optimal strategy change?