HackerRank Sherlock and the Valid String problem solution

YASH PAL,

In this HackerRank Sherlock and the Valid String Interview preparation kit problem solution, 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.

Function Description

Complete the isValid function in the editor below.

isValid has the following parameter(s):

  • string s: a string

Returns

  • string: either YES or NO
HackerRank Sherlock and the Valid String solution

HackerRank Sherlock and the Valid String problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the isValid function below.
def isValid(s):
    d = Counter(s)
    counts = Counter(d.values())
    if len(counts) == 1:
        return "YES"
    elif len(counts) > 2:
        return "NO"
    else:
        max_v = max(counts.values())
        k1, k2 = counts.keys()
        if (max_v == len(d) - 1):
            if (abs(k1 - k2) == 1):
                return "YES"
            elif (min(k1, k2) == 1):
                if counts[1] == 1:
                    return "YES"
                else:
                    return "NO"
            else:
                return "NO"
        else:
            return "NO"

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = input()

    result = isValid(s)

    fptr.write(result + 'n')

    fptr.close()

Sherlock and the Valid String problem solution in Java.

import java.io.*;
import java.util.*;
import java.math.BigInteger;
import java.util.Map.Entry;

import static java.lang.Math.*;

public class Solution extends PrintWriter {

	boolean solve() {

		char[] str = nextLine().toCharArray();

		int m = 256, n = str.length + 1;
		int[] cnt = new int[m];
		for (char c : str) {
			++cnt[c];
		}

		int[] f = new int[n];

		for (int val : cnt) {
			++f[val];
		}

		int x = 0;
		for (int i = 1; i < n; i++) {
			if (f[i] > 0) {
				++x;
			}
		}

		if (x == 1) {
			return true;
		}

		if (x > 2) {
			return false;
		}

		int y = 0;

		for (int i = 2; i < n; i++) {
			if (f[i] > 0) {
				++y;
			}
		}

		if (y == 1 && f[1] == 1) {
			return true;
		}

		int z = 0;

		for (int i = 2; i < n; i++) {
			if (f[i] == 1 && f[i - 1] > 0) {
				++z;
			}
		}

		return z == 1;
	}

	void run() {
		println(solve() ? "YES" : "NO");
	}

	int[][] nextMatrix(int n, int m) {
		int[][] matrix = new int[n][m];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				matrix[i][j] = nextInt();
		return matrix;
	}

	String next() {
		while (!tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(nextLine());
		return tokenizer.nextToken();
	}

	boolean hasNext() {
		while (!tokenizer.hasMoreTokens()) {
			String line = nextLine();
			if (line == null) {
				return false;
			}
			tokenizer = new StringTokenizer(line);
		}
		return true;
	}

	int[] nextArray(int n) {
		int[] array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = nextInt();
		}
		return array;
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	String nextLine() {
		try {
			return reader.readLine();
		} catch (IOException err) {
			return null;
		}
	}

	public Solution(OutputStream outputStream) {
		super(outputStream);
	}

	static BufferedReader reader;
	static StringTokenizer tokenizer = new StringTokenizer("");
	static Random rnd = new Random();

	public static void main(String[] args) throws IOException {
		Solution solution = new Solution(System.out);
		reader = new BufferedReader(new InputStreamReader(System.in));
		solution.run();
		solution.close();
		reader.close();

	}
}

Problem solution in C++ programming.

#include <bits/stdc++.h>

using namespace std;

char s[1234567];

int main() {
  scanf("%s", s);
  int n = strlen(s);
  vector <int> cnt(26, 0);
  for (int i = 0; i < n; i++) {
    cnt[s[i] - 'a']++;
  }
  for (int i = 0; i <= 26; i++) {
    if (cnt[i] == 0) {
      continue;
    }
    if (i < 26) {
      cnt[i]--;
    }
    vector <int> a = cnt;
    sort(a.begin(), a.end());
    int res = a[25];
    bool ok = true;
    for (int j = 0; j < 26; j++) {
      if (a[j] != 0 && a[j] != res) {
        ok = false;
        break;
      }
    }
    if (ok) {
      puts("YES");
      return 0;
    }
    if (i < 26) {
      cnt[i]++;
    }
  }
  puts("NO");
  return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int test(int *alphabet)
{
	int num = alphabet[0];
	int i;
	
	for(i = 1; i < 26; i++)
	{
	    if(alphabet[i] == num)
		{
			num = alphabet[i];
		}
		else if(alphabet[i] != num && alphabet[i] != 0)
			return 0;
	}
	return 1;
}


int main() {

	int i = 0;
	int alphabet[26];
	int c = EOF;
	int num, pass = 0;
	
	for(i = 0; i < 26; i++)
		alphabet[i] = 0;
	

	while (( c = getchar() ) != 'n' && c != EOF)
    {
        alphabet[c - '0' - 49]++;
    }

    if(test(alphabet))	
		printf("YESn");	
	else
	{
		for(i = 0; i < 26; i++)
		{
			if(i != 0)
				alphabet[i - 1]++;
	    	alphabet[i]--;
			if(test(alphabet))
			{
				printf("YESn");
			    pass = 1;
				break;
			}
		}
		if(pass == 0)
			printf("NOn");
	}

	return 0;
}

Problem solution in JavaScript programming.

function countHighest(high, array){
    var i = 0,
        counter = 0;

    for (i = 0; i < array.length; i++){
        if (array[i] === high){
            counter++;
        }
    }
    
    return counter;
}

function countLowest(low, array){
    var i = 0,
        counter = 0;

    for (i = 0; i < array.length; i++){
        if (array[i] === low){
            counter++;
        }
    }
    
    return counter;
}

function getLowestValue(alphaArr){
    var i = 0,
        low = -1;
    
    for (i = 0; i < alphaArr.length; i++){
        if (alphaArr[i] !== 0) {
            
           if (low === -1){
               low = alphaArr[i];
           } else if (low > alphaArr[i] ){
               low = alphaArr[i];
           }    
        }
    }
    
    return low;
}

function getHighestValue(alphaArr){
    var i = 0,
        high = 0;
    for (i = 0; i < alphaArr.length; i++){
        if (high < alphaArr[i]){
            high = alphaArr[i];
        }
    }
    
    return high;
}

function createAlphaArray(string){
    var i = 0,
        alphaArr = [];
    
    for (i = 0; i < 26; i++){
        alphaArr.push(0);
    }
    
    for (i = 0; i < string.length; i++){
        alphaArr[string.charCodeAt(i) - 97]++;
    }
    
    return alphaArr;
}

function processData(input) {
    var string = '',
        alpha = [],
        high = 0, low = 0,
        numberOfHighs = 0, numberOfLows = 0;
    
    string = input.split('n')[0];
    alpha = createAlphaArray(string);
    high = getHighestValue(alpha);
    low = getLowestValue(alpha);
    
   // console.log(alpha);
    
    // if the difference of high and low is greater than or equal to 2,
    // string immediately fails
    if (high - low >= 2){
        if (low === 1 && countLowest(low, alpha) === 1){
            console.log('YES');
        } else {
            console.log('NO');
        }
    } else if (high === low){
        console.log('YES');
    } else {
        numberOfHighs = countHighest(high, alpha);
        numberOfLows = countLowest(low, alpha);
        
        // if we have more highs than lows, we must check number of lows
        if (numberOfHighs > numberOfLows){
            if (numberOfLows === 1){
                console.log('YES');
            } else {
                console.log('NO');
            }
        } else if (numberOfLows > numberOfHighs){
            if (numberOfHighs === 1){
                console.log('YES');
            } else {
                console.log('NO');
            }
        } else if (numberOfLows === numberOfHighs){
            if (numberOfHighs === 1){
                console.log('YES');
            }
            else {
                console.log('NO');
            }
        }
    }
    
    //nsole.log('Highest: ' + high + ' | Lowest: ' + low);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

coding problems solutions Hackerrank Problems Solutions interview prepration kit