3016. Minimum Number of Pushes to Type Word II

String Greedy Sorting Hash Table Counting

Time: O(n + 26 log 26)

Space: O(26)

Intuition

Minimum number of operations to make string of length n where each character replaces its value. Operations = insertions of characters to satisfy constraints.

Algorithm

1Each character contributes to constraints on adjacent characters. Count required insertions.

Common Pitfalls

•Count consecutive characters needing insertions between them based on their difference.

3016.cs

// Approach: Frequency sort; assign highest-freq chars to fewest-press keys (8 chars per press tier).
// Time: O(n + 26 log 26) Space: O(26)

public class Solution
{
    public int MinimumPushes(string word)
    {
        int ans = 0;
        int[] count = new int[26];

        foreach (char ch in word)
            ++count[ch - 'a'];

        Array.Sort(count);

        for (int i = 0; i < 26; i++)
            ans += count[26 - i - 1] * (i / 8 + 1);

        return ans;
    }
}

Was this solution helpful?