STR1234 - Editorial

editorial
,
1

PROBLEM LINK :

Practice
Contest

Author : Maaz Bin Asad
Tester : Prasoon Jain
Editorialist : Prasoon Jain

DIFFICULTY :

CAKEWALK

PREREQUISITES :

Strings, frequency array

PROBLEM :

Given a string s consisting of only lowercase characters. You can perform following operation exactly once:
→ Choose any character from the English alphabets and remove some (or all) occurrences of this alphabet from the given string.
What is the smallest length of the string that you can obtain ?

QUICK EXPLANATION :

To get the smallest final string just remove all the occurrences of a character that appears maximum times in the string.

EXPLANATION :

→ You are asked to choose a character and remove some or all occurrences of it from the string. As you need to find the smallest string after above operation, it is very clear that we always have to remove all the occurrences of that chosen character.

→ Now, which character to choose ? Let x be our chosen character. Let n be the length of original length of the string. So after removing all occurrences of x, the length of final string will be (n-count(x)), where count(x) is the number of times x occurs in the string. We can clearly see for minimum final length, count(x) should me maximum. So, choose a character which occurs maximum time in the given string.

→ How to choose x ? Main part of the question is to choose optimum character. For that let’s make a frequency array freq[ ] of size of lowercase English letters. The size of the array will be 26. Now, iterate over the characters of given string and increase the count of that character by 1 in the frequency array by freq[ s[i] - ‘a’ ]++. Read more about frequency array here .

Now, just iterate over the freq[ ] array and choose the maximum value.
Final answer will be (length of original string - max).

TIME COMPLEXITY :

Time complexity is O(|S| +A ) per test case, where A=26, the size of freq[ ].

SOLUTIONS :

Editorialist's Solution

import java.util.Scanner;

class STR1234 {

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    sc.nextLine();
    while (t > 0) {
        String s = sc.nextLine();

        //calculating frequency of each character
        int freq[] = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }

        // max will store the frequency of maximum occuring element.
        
        int max = 0;
        for (int i = 0; i < 26; i++) {
            max = Math.max(freq[i], max);
        }
        System.out.println(s.length() - max);

        t--;
    }
    sc.close();
}

}

Feel Free to share and discuss your approach here.