Hard: Sherlock and valid string

# Hard: Sherlock and valid string

March 7, 2023 Name
Moch Lutfi
@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 mainimport ( "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)