O(N) solution using ListNode and HashMap


  • 0
    C

    1\ store all the characters in a list of listnode. The index+1 is their frequency.
    2\ each time you encounter a character, if it already exists, remove it from old index and add it to new index. else, add it to list[0].

    public class Solution {
        private class ListNode{
            public char val;
            public int count;
            public ListNode pre;
            public ListNode next;
            public ListNode(char c) { 
                this.val = c;
                count = 0;
                pre = null;
                next = null;
            }
        }
        public string FrequencySort(string s) {
            var memo = new List<ListNode>();
            var dic = new Dictionary<char, ListNode>();
            
            foreach(var c in s){
                if(!dic.ContainsKey(c)) dic.Add(c, new ListNode(c));
                var n = ++dic[c].count;
                if(n == 1){
                    AddNode(memo, dic[c], 0);
                }
                else{
                    RemoveNode(memo, dic[c], n-2);
                    AddNode(memo, dic[c], n-1);
                }
            }
            var N = memo.Count();
            var sb = new StringBuilder();
            for(var i = N-1; i >= 0; i--){
                var node = memo[i];
                while(node != null){
                    var j = i+1;
                    while(j > 0){
                        sb.Append(node.val);
                        j--;
                    }
                    node = node.next;
                }
            }
            return sb.ToString();
        }
        
        private void AddNode(IList<ListNode> memo, ListNode x, int idx){
            var N = memo.Count();
            if(idx == N){
                memo.Add(x);
            }
            else{
                x.next = memo[idx];
                if(memo[idx] != null){
                    memo[idx].pre = x;
                }
                memo[idx] = x;
            }
        }
        
        private void RemoveNode(IList<ListNode> memo, ListNode x, int idx){
            if(memo[idx] == x){
                memo[idx] = x.next;
                if(x.next != null){
                    x.next.pre = null;
                }
                x.next = null;
                x.pre = null;
            }
            else{
                x.pre.next = x.next;
                if(x.next != null){
                    x.next.pre = x.pre;
                }
                x.next = null;
                x.pre = null;
            }
        }
    }
    

Log in to reply
 

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