Sherlock and the Valid String

  • + 0 comments

    java

    public static String isValid(String s) {
                // Write your code here
                HashMap<Character , Integer> charFreq = new HashMap<>() ;
                for(char c:s.toCharArray())
                {
                    int count = charFreq.getOrDefault(c, 0) +1 ;
                    charFreq.put(c, count);
                }
                
                HashMap<Integer,Integer> freqCount = new HashMap<>();
                //freq => count 
                // 2   => 2   : aabbccc (a freq = 2 and b freq =2 so freq 2 => have count 2)  
                for(int freq : charFreq.values())
                {
                    int count = freqCount.getOrDefault(freq , 0)+1 ;
                    freqCount.put(freq , count);
                }
                
                if(freqCount.size() == 1)
                {
                    return "YES" ;
                }
                
                if(freqCount.size() == 2)
                {
                    int i =0 , f1 = 0 , f2 = 0 , c1 = 0 , c2 = 0 ;
                    for(int freq : freqCount.keySet())
                    {
                        if(i == 0)
                        {
                            f1 = freq ;
                            c1 = freqCount.get(freq);
                        }else{
                            f2 = freq ;
                            c2 = freqCount.get(freq);
                        }
                        i++ ;
                    }
                    
                    if((c1 == 1 && f1 == 1) || (c2 == 1 && f2 == 1))
                    { 
                        //int this condition size == 2 (only 2 frequecy)
                        // so if any freq == 1 and it's count == 1
                        // then if we remove that so it become valid 
                        // so it's a "YES" 
                        return "YES";
                    }
                    
                    if(Math.abs(f1 -f2) == 1)
                    {
                        //frequecy diffrence should be 1 
                        // example f1 = 2 and f2 = 3 => so if we remove 1 from f2 
                        // f2 = (3 -1) = 2 
                        // it can be  become valid string 
                        // can be not deffinatly 
                        /*
                            The two frequencies differ by exactly 1
                            The higher frequency (3) appears only once
                            We can remove 1 character from higher frequency
                             to make its frequency = 2
                             All characters would then have frequency 2
                        */
                                           
                        if((c1 == 1 && f1 > f2) || (c2 == 1 && f2 > f1))
                        {
                            /*
                            //eg => "aabbb"(true)
                                f1 = 2 , c1 = 1
                                f2 = 3 ,c2 = 1
                            
                             or "aabbbccc" (false)
                             f1 = 2 , c1 = 1 
                             f2 = 3 , c2 = 2
                             */
                             // if count = 1 
                             //then it freqncy shoubld be greter (+1)
                             //becouse remove there by one make the string valid 
                             //if count = 1 and freqncy is smaller ex => 2
                             // then even 2-1 = 1 
                             // one charecter still left 
                             //so not a valid string 
                            return "YES";
                        }
                    }
                    
                }
                
               
                return "NO"; // if freqCount greter than 2 then it's not valid 
                            // eg. => 2 , 1 , 3 => not valid
    
            }