O(n * log(n)) Solution Using Array.Sort with Custom Comparer


  • 0
    R
    1. Count the chars in a map
    2. Create an array of CharCount objects
    3. Define a custom comparer to sort this array of objects by decreasing "count"
    4. Construct the result string.
    public class Solution 
    {
        class CharCount
        {
            public char ch;
            public int cnt;
            
            public CharCount(char ch, int cnt)
            {
                this.ch = ch;
                this.cnt = cnt;
            }
        }
        
        private class CharComparer:IComparer
        {
            public int Compare(object obj1, object obj2)
            {
                CharCount c1 = (CharCount)obj1;
                CharCount c2 = (CharCount)obj2;
                
                // Reverse the 1 & -1 to sort in decreasing order
                if(c1.cnt > c2.cnt)
                    return -1;
                    
                else if(c1.cnt < c2.cnt)
                    return 1;
                    
                return 0;   
            }
        }
        
        public string FrequencySort(string s) 
        {
            Dictionary<char,int> mapcount = new Dictionary<char,int>();
            
            for(int i = 0; i < s.Length; ++i)
            {
                if(!mapcount.ContainsKey(s[i]))
                    mapcount.Add(s[i], 0);
                
                ++mapcount[s[i]];
            }
            
            CharCount[] arr = new CharCount[mapcount.Count];
            int idx = 0;
            foreach(var pair in mapcount)
            {
                arr[idx] = new CharCount(pair.Key, pair.Value);
                ++idx;
            }
            
            CharComparer comparer = new CharComparer();
            Array.Sort(arr, comparer);
            
            StringBuilder res = new StringBuilder();
            
            foreach(var c in arr)
            {
                for(int i = 0; i < c.cnt; ++i)
                    res.Append(c.ch);
            }
            
            return res.ToString();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.