mediumStringsPattern: Random
Chef's Ingredient Rearrangement Solution
Problem Statement
Given two strings of ingredients, s1 and s2, of the same length, determine the minimum number of swap operations on the characters of s1 to transform it into s2. Each swap operation can exchange two characters in s1. The input strings can be modified, and additional space can be used for bookkeeping. If it is impossible to transform s1 into s2, return -1.
Examples
Example 1:
Input:{"s1":"abc","s2":"bca"}
Output:2
Explanation: To transform 'abc' into 'bca', we need to perform two swap operations: swap 'a' and 'b', then swap 'a' and 'c' (or alternatively, swap 'b' and 'c', then swap 'a' and 'b')
Example 2:
Input:{"s1":"xyxz","s2":"yxzx"}
Output:3
Explanation: To transform 'xyxz' into 'yxzx', we need to perform three swap operations: swap 'x' and 'y', then swap 'y' and 'x', then swap 'x' and 'z'
Example 3:
Input:{"s1":"aaa","s2":"aaa"}
Output:0
Explanation: The strings are already identical
Example 4:
Input:{"s1":"abc","s2":"def"}
Output:-1
Explanation: It is impossible to transform 'abc' into 'def' because they have different characters
Constraints
- 1 <= length of s1 == length of s2 <= 100
- s1 and s2 contain only lowercase English letters
- The input strings can be modified, and additional space can be used for bookkeeping
Time: O(n) Space: O(n)
An optimized approach is to use a cycle detection algorithm to find the minimum number of swap operations, resulting in a time complexity of O(n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.