Minimum Number of Steps to Make Two Strings Anagram
LeetCode 1347: Minimum Number of Steps to Make Two Strings Anagram
Problem Description
Given two strings s and t of the same length, you want to change t in the minimum number of steps such that it becomes an anagram of s. A step consists of replacing one character in t with another character.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, "anagram" and "nagaram" are anagrams.
Both strings consist of lowercase English letters.
Example 1: Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is an anagram of s.
Example 2: Input: s = "leetcode", t = "practice" Output: 5 Explanation: Replace 'p', 'r', 'a', 'i', 'c' in t with 'l', 'e', 'e', 't', 'd' to form an anagram of s.
Example 3: Input: s = "anagram", t = "mangaar" Output: 0 Explanation: "anagram" is already an anagram of "mangaar".
Solution in Go
The core idea to solve this problem is to count the frequency of each character in both strings s and t. Since we want to transform t into an anagram of s by replacing characters in t, we need to identify characters in t that are "excess" compared to what s needs.
For each character from 'a' to 'z':
- Count its occurrences in
s. - Count its occurrences in
t. - If the count of a character in
tis greater than its count ins, it meansthast_count - s_countextra occurrences of this character. These extra occurrences must be replaced to match the character distribution ofs. - The sum of these differences for all characters will give us the minimum number of steps.
This approach works because we only care about the characters that are overrepresented in t. Any characters that are underrepresented in t (i.e., t_count < s_count) will be formed by replacing the overrepresented characters. The total number of replacements needed is exactly the sum of the excesses.
package main import "fmt" func minSteps(s string, t string) int { sFreq := make([]int, 26) // Frequency array for string s tFreq := make([]int, 26) // Frequency array for string t // Populate frequency array for string s for _, char := range s { sFreq[char-'a']++ } // Populate frequency array for string t for _, char := range t { tFreq[char-'a']++ } steps := 0 // Compare frequencies and calculate steps for i := 0; i < 26; i++ { // If character 'i' appears more times in t than in s, // these are the characters that need to be changed. if tFreq[i] > sFreq[i] { steps += tFreq[i] - sFreq[i] } } return steps } func main() { // Test cases fmt.Println(minSteps("bab", "aba")) // Expected: 1 fmt.Println(minSteps("leetcode", "practice")) // Expected: 5 fmt.Println(minSteps("anagram", "mangaar")) // Expected: 0 fmt.Println(minSteps("xxyyzz", "xxyyzz")) // Expected: 0 fmt.Println(minSteps("friend", "family")) // Expected: 4 }Hashmap Solution
package main import ( "fmt" ) func minSteps(s string, t string) int { m := map[string]int{} for i := 0; i < len(s); i++ { m[string(s[i])]++ } for i := 0; i < len(t); i++ { m[string(t[i])]-- } steps := 0 for _, v := range m { steps += abs(v) } return steps / 2 } func abs(x int) int { if x < 0 { return -x } return x } func main() { fmt.Println(minSteps("bab", "aba")) fmt.Println(minSteps("leetcode", "practice")) fmt.Println(minSteps("anagram", "mangaar")) fmt.Println(minSteps("xxyyzz", "xxyyzz")) fmt.Println(minSteps("friend", "family")) }