DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Longest Happy String

Problem

TC: O(nlogn)

//greedily try to add char one by one, in the final string, don't try and add 2 char at a time else we might miss a potential longer possible string in future
class Solution {
    public String longestDiverseString(int a, int b, int c) {
        Queue<Pair> q = new PriorityQueue<>((p,r)-> Integer.compare(r.f,p.f));
        if(a>0)
        q.add(new Pair('a',a));
        if(b>0)
        q.add(new Pair('b',b));
        if(c>0)
        q.add(new Pair('c',c));

        StringBuilder sb = new StringBuilder();

        while(!q.isEmpty()){
            Pair p1  = null;
            //can we use the current char at top of the q ?
            //if below is true then we can't use the top char ( as it has appeared 2 times cotinuously at the end )
            if(sb.length()>=2 && sb.charAt(sb.length()-1)==q.peek().c && sb.charAt(sb.length()-2) ==q.peek().c){
                p1 = q.remove();//meaning we can not use the to char yet
                if(q.isEmpty()) break;
            }
            //if we use or not use the top char in q, next char can definetly be used
            Pair p2 = q.remove();
            sb.append(p2.c);
            p2.f--;
            if(p2.f>0){
                q.add(p2);
            }
            if(p1!=null)q.add(p1);
        }
        return sb.toString();

    }
}
class Pair{
    char c ;
    int f;
    public Pair(char c, int f){
        this.c = c;
        this.f = f;
    }
    public String toString(){
        return "["+this.c+","+this.f+"]";
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)