We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Sherlock and the Valid String
  5. Discussions

Sherlock and the Valid String

Sort by

recency

|

2049 Discussions

|

  • tan_191
     + 0 comments

    Java 15 solution that passes all test cases:

    public static String isValid(String s) {
    HashMap<Character, Integer> charFreqs = new HashMap<Character, Integer>();
    
    for (int i = 0; i < s.length(); i++) { //Get the frequencies of each character
        char a = s.charAt(i);
        if (charFreqs.containsKey(a)) charFreqs.replace(a, charFreqs.get(a) + 1);
        else charFreqs.put(a,1);
    }
    List<Integer> freqList = new ArrayList<Integer>();
    boolean safeToRemove = true; //Flag for if we've already removed a single character
    
    for (char key : charFreqs.keySet()) { //Create a list of all character frequencies, then sort it
        freqList.add(charFreqs.get(key));
    }
    Collections.sort(freqList);
    int minFreq = freqList.get(0); //The minimum frequency that isn't 1 is our target value, since we can only remove characters from the string.
    if (minFreq == 1) { //If there's a single instance of a given character...
        safeToRemove = false;
        if (freqList.size() > 1) minFreq = freqList.get(1); //...use the second frequency if the list of frequencies has more than one element.
    }
    
    for (int j = 1; j < freqList.size(); j++) {
        int freq = freqList.get(j);
        System.out.println(freq);
        if (freq == 1 && !safeToRemove) return "NO"; //There are multiple characters for which only one instance occurs.
        else if (freq - minFreq == 1) { //If we've already removed a character, we can't remove another. So check if we didn't already do so and then set that flag to false if such is the case.
            if (safeToRemove) safeToRemove = false;
            else return "NO";
        } else if (freq - minFreq > 1) return "NO"; //If a frequency exists that's greater than 1 + the minimum frequency, the string isn't valid.
    }
    
    return "YES";
}

  • biren_yadav114
     + 0 comments

    python -

    def isValid(s):

    # Write your code here
s_dict = {}
count=0
for i in s:
    if i in s_dict:
        s_dict[i]+=1
    else:
        s_dict[i]=1
dict_val_list = list(s_dict.values())

for i in range(1,len(s_dict)):
    if dict_val_list[0] == dict_val_list[i]:
        continue          
    else:
        if count==0:
            count+=1
        else:
            return 'NO'
return 'YES'

  • Peace_Ranger
     + 0 comments

    The input "aabbbccc" is not a valid one cz at least 2 characters has to be removed to make this valid. But the editorial solutions consider this input as "valid". How's that possible? Am I missing something obvious here?

  • priyanshugevra
     + 0 comments
     public static String isValid(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int n = s.length();
        for(int i=0 ; i<n ; i++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0)+1);
        } 
        Map<Integer,Integer> freqMap = new HashMap<>();
        for(int fq : map.values())
        {
            freqMap.put(fq, freqMap.getOrDefault(fq, 0)+1);
        }
          if (freqMap.size() == 1) {
            return "YES"; 
        }
          if (freqMap.size() == 2) {
            for(int i : freqMap.values()){
                if(i==1) return "YES";
            }
        }

                can any one explain why it is paasing only 18/20 test cases? also please give the failed test case.

            `        
    return "NO";

}

  • highsoft_soi
     + 0 comments

    Perl:

    sub isValid {
    my @s = split("", shift);
    
    my %h;
    my %c;

    foreach (@s) {
        $h{$_} +=1;
    }
    foreach (values(%h)) {
        $c{$_} +=1;
    }

    return "YES" if (keys(%c) == 1);    
    
    if (keys %c == 2) {
        my @keys = keys(%c);
        my ($freq1, $freq2) = @keys;
        my ($count1, $count2) = @c{@keys};

        if (($freq1 == 1 && $count1 == 1) || ($freq2 == 1 && $count2 == 1)) {
            return "YES";
        }

        if ((abs($freq1 - $freq2) == 1) && ($count1 == 1 || $count2 == 1)) {
            return "YES";
        }
    }

    return "NO";
}