String Manipulation | Sherlock and the Valid String

In this blog we are discussing problem on string manipulation posted on HackerRank.

Problem:

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just 1 character at 1 index in the string, and the remaining characters will occur the same number of times. Given a string s, determine if it is valid. If so, return YES, otherwise return NO.

For example, if s = abc, it is a valid string because frequencies are {a : 1, b : 1, c : 1} . So is s = abcc because we can remove one c and have 1 of each character in the remaining string. If s = abccc however, the string is not valid as we can only remove 1 occurrence of c. That would leave character frequencies of {a : 1, b : 1, c : 2}.

Function Description: Complete the isValid function in the editor below. It should return either the string YES or the string NO. isValid has the following parameter(s):

• s : a string

Input Format:

A single string s.

Constraints:

• 1 <= | s | <= 10^5

• Each character s[ i ] -> ASCII [a - z]

Output Format:

Print YES if string s is valid, otherwise, print NO.

Sample Input 0:

aabbcd 

Sample Output 0:

NO 

Explanation 0: Given s = "aabbcd", we would need to remove two characters, both c and d -> aabb or a and b -> abcd, to make it valid. We are limited to removing only one character, so s is invalid.

Sample Input 1:

aabbccddeefghi 

Sample Output 1:

NO 

Explanation 1: Frequency counts for the letters are as follows: {'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2, 'f': 1, 'g': 1, 'h': 1, 'i': 1} There are two ways to make the valid string:

• Remove characters with a frequency of 1:{f g h i} .

• Remove characters of frequency 2:{a b c d e} .

Neither of these is an option.

Sample Input 2:

abcdefghhgfedecba 

Sample Output 2

YES 

Explanation 2 All characters occur twice except for e which occurs 3 times. We can delete one instance of e to have a valid string.

---

Implementation Using Java:

import java.io.*;
import java.util.*;

public class Solution {

    static String isValid(String s) {
    
        int[] f = new int[26];

        for(char c : s.toCharArray()){
            f[c-'a']++;
        }
        if(s.length() == 1){
            return "YES";
            
        }
        for(int i = 0;i < 26;i++){
            long count = 0;

            for(int j = 0;j < 26;j++){
                if(f[i] < f[j]){
                    count += f[j]-f[i];
                }
                else if(f[j] < f[i]){
                    count += f[j];
                }
            }
            if(count <= 1)
            {
                return "YES";
            }
        }
        return "NO";
}

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        
        String s = scanner.nextLine();

        String result = isValid(s);

        System.out.println(result);
       
        scanner.close();
    }
}

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem

Follow Programmers Door for more.

#blog #interview #placement #hackerrank #coding