Published on

# Hard: Sherlock and valid string

Authors

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.

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
`_59package main_59_59import (_59 "testing"_59)_59_59func isValid(s string) string {_59 kind := make(map[rune]int)_59 for _, ch := range s {_59 kind[ch]++_59 }_59_59 if len(kind) == 1 {_59 return "YES"_59 }_59_59 freq := map[int]int{}_59 for _, v := range kind {_59 freq[v]++_59_59 }_59 max := -9999_59 mainFreq := 0_59 for k, v := range freq {_59 if v > max {_59 max = v_59 mainFreq = k_59 }_59 }_59_59 hasUniqFreq := false_59_59 for _, freq := range kind {_59 if freq != mainFreq {_59 if hasUniqFreq || freq-mainFreq != 1 && freq != 1 {_59 return "NO"_59 } else {_59 hasUniqFreq = true_59 }_59 }_59 }_59 return "YES"_59}_59_59func TestLastIndex(t *testing.T) {_59 tests := []struct {_59 input string_59 want string_59 }{_59 {input: "aabbc", want: "YES"},_59 {input: "aabbcd", want: "NO"},_59 {input: "abcdefghhgfedecba", want: "YES"},_59 }_59 for _, tt := range tests {_59 if got := isValid(tt.input); got != tt.want {_59 t.Errorf("isValid(%v) = %v, want %v", tt.input, got, tt.want)_59 }_59 }_59}`

Try it yourself https://go.dev/play/p/jtD3sCn5LkJ