Hard: Sherlock and valid string

Hard: Sherlock and valid string

March 7, 2023

Moch Lutfi
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:

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

Solution

  1. Init map then find out how many repetition of char
  2. Return YES if string input consist of 1 char only such as "aaaa" or "bbb" or "zz"
  3. Init another map to find out how many char with X frequency
  4. Find the most frequencies occurred
  5. Iterate from the first map kind
  6. Check if the current frequency is different with mainFreq
  7. Return NO if hasUniqFreq or different frequency more than 1, otherwise set hasUniqFreq true
  8. 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)