The Valid String

Lintcode 1893. The Valid String

We consider a string to be valid if all characters of the string appear the same number of times. It is also valid if we 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.

1 ≤ |s| ≤ 100000 Each character s[i] ∈{‘a' - ’z'}

Example 1

Input: aabbcd
Output: NO
Explanation:we would need to remove two characters, both 'c' and 'd' —>'aabb' or 'a' and 'b' —> 'abcd', to make it valid. We are limited to removing only one character so it is "NO".

My Solutions:

先对所有字母的频率计数，再遍历所有字母，计算频率的值（first/second）以及个数(sum_first/sum_second)。因为要满足所有字母都是一个频率且最多只能删去一个字母，只能有以下几个情况：

• 所有字母都是一个频率first

• 只有一个字母是频率first，其他字母都是频率second，且

  • first=1或者first==second+1，这样只要删去一个字母

• 只有一个字母是频率second，其他字母都是频率first，且

  • second=1或者second=first+1

public class Solution {
    /**
     * @param s: a string
     * @return: if valid return "YES" else return "NO"
     */
    public String isValid(String s) {
        // write your code here
        if (s == null || s.length() <= 3) return "YES";
        int[] hash = new int[26];
        for (char c : s.toCharArray()) hash[c - 'a']++;

        int first = 0, second = 0;
        int sum_first = 0, sum_second = 0;
        for (int i = 0; i < 26; i++) {
            if (hash[i] == 0) continue;
            if (first == 0) {
                first = hash[i];
                sum_first = 1;
            } else if (hash[i] == first) {
                sum_first++;
            } else if (second == 0) {
                second = hash[i];
                sum_second = 1;
            } else if (hash[i] == second) {
                sum_second++;
            } else
                return "NO";
        }

        if (second == 0) return "YES";
        if ((first == 1 || first == second + 1) && sum_first == 1) return "YES";
        if ((second == 1 || second == first + 1) && sum_second == 1) return "YES";

        return "NO";
    }
}