Leetcode 2186: Minimum Number of Steps to Make Two Strings Anagram II

Input: The input consists of two strings s and t.

Example: Input: s = 'listen', t = 'silent'

Constraints:

• 1 <= s.length, t.length <= 2 * 10^5

• s and t consist of lowercase English letters.

Output: Return the minimum number of steps required to make s and t anagrams of each other.

Example: Output: 0

Constraints:

• Both s and t consist only of lowercase English letters.

Goal: Calculate the number of steps to make s and t anagrams by appending characters.

Steps:

• Count the frequency of each character in s and t.

• Calculate the difference in frequencies for each character.

• Sum up the absolute differences in frequencies to determine the minimum steps.

Goal: Conditions that the solution must satisfy.

Steps:

• The lengths of both strings are between 1 and 2 * 10^5.

• Both strings contain only lowercase English letters.

Assumptions:

• Both strings contain only lowercase letters.

• The strings s and t are not empty.

• Input: Input: s = 'listen', t = 'silent'

• Explanation: The two strings are already anagrams, so no additional steps are required. Thus, the output is 0.

• Input: Input: s = 'abc', t = 'def'

• Explanation: The characters 'a', 'b', 'c' need to be removed from s and 'd', 'e', 'f' need to be removed from t. Thus, 6 steps (3 from each string) are required.

Approach: We will count the frequency of characters in both strings, then compare these frequencies to calculate how many characters need to be added or removed to balance them.

Observations:

• If the strings are already anagrams, no steps are needed.

• The key idea is to count character occurrences and calculate the differences to figure out how many operations are required.

Steps:

• Count the frequency of each character in s and t.

• For each character, calculate the absolute difference in counts.

• Sum the differences to get the total number of steps needed.

Empty Inputs:

• If either string is empty, the result is the length of the other string, since we need to add all its characters.

Large Inputs:

• The solution must efficiently handle strings with lengths up to 200,000.

Special Values:

• Strings that are already anagrams will require 0 steps.

Constraints:

• The solution should efficiently compute the result without excessive time complexity.

int minSteps(string s, string t) {
    vector<int> tsk(26, 0);
    for(char c: s)
    tsk[c - 'a']++;
    for(char c: t)
    tsk[c - 'a']--;

    int ans = 0;
    for(int a: tsk) ans += abs(a);
    return ans;
}

1 : Function Definition

int minSteps(string s, string t) {

This defines the function `minSteps`, which takes two input strings, `s` and `t`, and calculates the minimum steps to convert `s` into `t` by modifying the characters.

2 : Vector Initialization

    vector<int> tsk(26, 0);

A vector `tsk` of size 26 is initialized to store the frequency difference of each character between the two strings. Each index corresponds to a letter from 'a' to 'z'.

3 : Loop through String `s`

    for(char c: s)

This loop iterates through each character `c` in the string `s`.

4 : Update Frequency for `s`

    tsk[c - 'a']++;

For each character `c` in `s`, the corresponding frequency count in the `tsk` vector is incremented, where the index is calculated by subtracting 'a' from `c`.

5 : Loop through String `t`

    for(char c: t)

This loop iterates through each character `c` in the string `t`.

6 : Update Frequency for `t`

    tsk[c - 'a']--;

For each character `c` in `t`, the corresponding frequency count in the `tsk` vector is decremented.

7 : Variable Initialization

    int ans = 0;

The variable `ans` is initialized to 0. It will hold the total number of character modifications needed to transform string `s` into string `t`.

8 : Summing Absolute Differences

    for(int a: tsk) ans += abs(a);

This loop sums the absolute values of the differences in character frequencies stored in the `tsk` vector. Each non-zero value in `tsk` indicates the number of steps needed for that character.

9 : Return Result

    return ans;

The function returns the total number of modifications (`ans`) required to convert string `s` into string `t`.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of the strings, since we are counting characters in each string and then summing the differences.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we only need a constant amount of extra space to store character frequencies.

Leetcode 2186: Minimum Number of Steps to Make Two Strings Anagram II

Explore →