You are given a string s
consisting only of lowercase English letters.
In one move, you can select any two adjacent characters of s
and swap them.
Return the minimum number of moves needed to make s
a palindrome.
Note that the input will be generated such that s
can always be converted to a palindrome.
Example 1:
Input: s = "aabb"
Output: 2
Explanation:
We can obtain two palindromes from s, "abba" and "baab".
- We can obtain "abba" from s in 2 moves: "aab<u>b</u>" -> "ab<u>ab</u>" -> "abba".
- We can obtain "baab" from s in 2 moves: "aa<u>b</u>b" -> "a<u>ba</u>b" -> "baab".
Thus, the minimum number of moves needed to make s a palindrome is 2.
Example 2:
Input: s = "letelt"
Output: 2
Explanation:
One of the palindromes we can obtain from s in 2 moves is "lettel".
One of the ways we can obtain it is "lete<u>lt</u>" -> "let<u>et</u>l" -> "lettel".
Other palindromes such as "tleelt" can also be obtained in 2 moves.
It can be shown that it is not possible to obtain a palindrome in less than 2 moves.
Constraints:
1 <= s.length <= 2000
s
consists only of lowercase English letters.s
can be converted to a palindrome using a finite number of moves.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force way to find the fewest moves to make a string a palindrome involves exploring all possible swap combinations. We try every possible ordering of characters and, for each arrangement, check how many swaps are needed to turn it into a palindrome. Then, we pick the ordering that requires the fewest swaps.
Here's how the algorithm would work step-by-step:
import itertools
def minimum_moves_to_make_palindrome_brute_force(input_string):
minimum_swaps = float('inf')
# Generate all possible permutations of the string
for permutation_tuple in itertools.permutations(input_string):
permutation_string = ''.join(permutation_tuple)
# Calculate swaps needed to make current permutation a palindrome
swaps_needed = calculate_swaps_to_make_palindrome(permutation_string)
# Track minimum swaps found so far
minimum_swaps = min(minimum_swaps, swaps_needed)
return minimum_swaps
def calculate_swaps_to_make_palindrome(input_string):
string_list = list(input_string)
swaps_count = 0
left_index = 0
right_index = len(string_list) - 1
while left_index < right_index:
if string_list[left_index] == string_list[right_index]:
left_index += 1
right_index -= 1
else:
# Find matching character from right side
temporary_index = right_index
while temporary_index > left_index and string_list[temporary_index] != string_list[left_index]:
temporary_index -= 1
# No matching character, string can't be palindrome
if temporary_index == left_index:
return float('inf')
else:
# Shift characters to make a match
for index_to_shift in range(temporary_index, right_index):
string_list[index_to_shift], string_list[index_to_shift + 1] = string_list[index_to_shift + 1], string_list[index_to_shift]
swaps_count += 1
left_index += 1
right_index -= 1
return swaps_count
The goal is to rearrange a string into a palindrome with the fewest swaps. The best way to do this is to match characters from the outside in, moving characters only when necessary.
Here's how the algorithm would work step-by-step:
def minimum_moves_to_make_palindrome(input_string):
input_list = list(input_string)
left_pointer = 0
right_pointer = len(input_list) - 1
move_count = 0
while left_pointer < right_pointer:
# If chars match, move inward.
if input_list[left_pointer] == input_list[right_pointer]:
left_pointer += 1
right_pointer -= 1
else:
index_to_swap = right_pointer
while index_to_swap > left_pointer and input_list[index_to_swap] != input_list[left_pointer]:
index_to_swap -= 1
# No matching char found.
if index_to_swap == left_pointer:
move_count += right_pointer - left_pointer
input_list[left_pointer], input_list[left_pointer + 1] = input_list[left_pointer + 1], input_list[left_pointer]
# Swap matching char.
else:
# Swap chars to make palindrome.
while index_to_swap < right_pointer:
input_list[index_to_swap], input_list[index_to_swap + 1] = input_list[index_to_swap + 1], input_list[index_to_swap]
move_count += 1
index_to_swap += 1
left_pointer += 1
right_pointer -= 1
return move_count
Case | How to Handle |
---|---|
Null or empty string input | Return 0 immediately as an empty string is considered a palindrome. |
String with a single character | Return 0, as a single-character string is already a palindrome. |
String with all identical characters (e.g., 'aaaa') | Return 0, since the string is already a palindrome. |
String where a palindrome can't be formed (e.g., 'abc') | Return -1 (or throw an exception) to indicate that a palindrome cannot be formed. |
Very long strings (performance implications) | Ensure the algorithm's time complexity is optimized to avoid timeouts; aim for O(n^2) or better if possible. |
String with mixed case characters (e.g., 'Racecar') | Convert the string to lowercase (or uppercase) before processing to ensure case-insensitive comparison. |
String with non-alphanumeric characters (e.g., 'A man, a plan, a canal: Panama') | Remove non-alphanumeric characters or ignore them during palindrome checking. |
String with mostly matching pairs except for one character in the middle (e.g. 'abcdcbea') | The algorithm must handle the single unmatched middle character appropriately, shifting it to the center. |