Frequency counting for a linear-time algorithm

Frequency counting is a powerful technique in algorithms design. It comes often when we're dealing with a small subset of data, such as lower-case alphabet letters. The problem below exemplifies it. Instead of removing characters one by one, the idea is to do a frequency counting and subsequently create the final string based on the max frequency. Code is down below, cheers, ACC.

Apply Operations to Make String Empty - LeetCode

3039. Apply Operations to Make String Empty

Medium

You are given a string s.

Consider performing the following operation until s becomes empty:

• For every alphabet character from 'a' to 'z', remove the first occurrence of that character in s (if it exists).

For example, let initially s = "aabcbbca". We do the following operations:

• Remove the underlined characters s = "aabcbbca". The resulting string is s = "abbca".
• Remove the underlined characters s = "abbca". The resulting string is s = "ba".
• Remove the underlined characters s = "ba". The resulting string is s = "".

Return the value of the string s right before applying the last operation. In the example above, answer is "ba".

 

Example 1:

Input: s = "aabcbbca"
Output: "ba"
Explanation: Explained in the statement.

Example 2:

Input: s = "abcd"
Output: "abcd"
Explanation: We do the following operation:
- Remove the underlined characters s = "abcd". The resulting string is s = "".
The string just before the last operation is "abcd".

 

Constraints:

• 1 <= s.length <= 5 * 105
• s consists only of lowercase English letters.

public string LastNonEmptyString(string s)
{
    int max = 0;
    Hashtable count = new Hashtable();

    foreach (char c in s)
    {
        if (!count.ContainsKey(c)) count.Add(c, 0);
        count[c] = (int)count[c] + 1;

        max = Math.Max(max, (int)count[c]);
    }

    string candidates = "";
    foreach (char c in count.Keys)
    {
        if ((int)count[c] == max)
        {
            candidates += c.ToString();
        }
    }

    string retVal = "";
    for (int i = s.Length - 1; i >= 0; i--)
    {
        if (candidates.Contains(s[i]))
        {
            retVal = s[i].ToString() + retVal;
            candidates = candidates.Replace(s[i], '*');
        }
    }

    return retVal;
}