Hard: Sherlock and valid string

March 7, 2023

Name: Moch Lutfi
Twitter: @kaptenupi

Question: Given a string, Sherlock considers it valid if all the characters in the string occur the same number of time. However, a string is also valid if the frequencies are same after removing any one character.

Example 1:
Input: str = “aabbcd”
Output: NO

Example 2:
Input: str = “abcc”
Output: YES

Problem statement

Let's break down the problem statement (opens in a new tab).

Sherlock needs to verify if a given string is valid. A string is valid under 2 conditions:

All characters of the string have same frequencies
If you can delete any one character from the string to achieve condition #1.

Solution

Init map then find out how many repetition of char
Return YES if string input consist of 1 char only such as "aaaa" or "bbb" or "zz"
Init another map to find out how many char with X frequency
Find the most frequencies occurred
Iterate from the first map kind
Check if the current frequency is different with mainFreq
Return NO if hasUniqFreq or different frequency more than 1, otherwise set hasUniqFreq true
Return YES

solution.go

package main
import (
	"testing"
)
func isValid(s string) string {
	kind := make(map[rune]int)
	for _, ch := range s {
		kind[ch]++
	}
	if len(kind) == 1 {
		return "YES"
	}
	freq := map[int]int{}
	for _, v := range kind {
		freq[v]++
	}
	max := -9999
	mainFreq := 0
	for k, v := range freq {
		if v > max {
			max = v
			mainFreq = k
		}
	}
	hasUniqFreq := false
	for _, freq := range kind {
		if freq != mainFreq {
			if hasUniqFreq || freq-mainFreq != 1 && freq != 1 {
				return "NO"
			} else {
				hasUniqFreq = true
			}
		}
	}
	return "YES"
}
func TestLastIndex(t *testing.T) {
	tests := []struct {
		input string
		want  string
	}{
		{input: "aabbc", want: "YES"},
		{input: "aabbcd", want: "NO"},
		{input: "abcdefghhgfedecba", want: "YES"},
	}
	for _, tt := range tests {
		if got := isValid(tt.input); got != tt.want {
			t.Errorf("isValid(%v) = %v, want %v", tt.input, got, tt.want)
		}
	}
}

Try it yourself https://go.dev/play/p/jtD3sCn5LkJ (opens in a new tab)

Staircase problem Decimal benchmark