[ETC.] HackerRank Algorithms in Java ‘Sherlock and the Valid String’ solution

Problem

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he 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. For example, if s = abc, it is a valid string because frequencies are {a:1, b:1, c:1}. So is s = abcc because we can remove one c and have 1 of each character in the remaining string. If s = abccc however, the string is not valid as we can only remove 1 occurrence of c. That would leave character frequencies of {a:1, b:1, c:1}.

Sample Input 0

aabbcd

Sample Output 0

NO

Solution

※ 이곳의 도움을 받았다. (https://stackoverflow.com/questions/51569165/sherlock-and-the-valid-string-giving-me-wrong-results-in-5-test-cases) 하지만 여기 코드를 그대로 치면 오류가 난다.
Thank you, MC Emperor. Your idea was very helpful :)

• 우선 String s의 각 문자별로 중복되는 횟수를 구한다. collect(Collectors.groupingBy(Function.identity(), Collectors.counting())) 여기서 Function을 사용하려면 반드시 ‘java.util.function.Function’을 임포트해야한다. 해커랭크에서 이미 import java.util.*;를 했지만 런타임 오류가 났다. 따로 추가해주니 해결되었다.
• 모아진 횟수를 또 다시 모으는데, 같은 횟수끼리 묶어준다.
• 만약 맵의 크기가 1이라면 모든 문자가 동일한 횟수로 등장하므로 “YES”를 반환한다.
• 만약 맵의 크기가 2 이상이라면, 어떤 문자들은 a만큼 등장하는데 어떤 문자는 b만큼 어떤 문자는 c만큼…. 이란 의미이므로 ‘한 번만 문자를 수정할 수 있다’는 조건에 위배되므로 “NO”를 반환한다.
• 만약 맵의 크기가 2라면 우선 문자들의 등장 횟수인 맵의 key값을 가져온다. 그게 1인데 value가 1이 아니라는 건, 어떤 문자들은 한 번씩 등장하는데 그게 여러 문자라는 것이다. 즉, 하나의 문자만 지운다고 해서 모든 문자가 동일한 횟수로 등장하는 것이 아니기 때문에 “NO”를 반환한다.
• 등장 횟수의 차이가 1이상이면 (예를 들어 어떤 문자는 4번 등장하는데 어떤 문자는 2번 등장한다는 등), 이미 앞에서 등장횟수 중에 1이 없다는 것이 판명 났으므로 해당 문자를 하나 더 추가한다고 해서 문제가 해결되지 않는다. “NO” 반환.
• 차이는 1이지만, 그만큼 등장하는 문자의 수가 1 이상이면 (2번씩 등장하는 문자가 8개, 1번씩 등장하는 문자가 2개일때) 역시 문자 하나를 수정해도 해결되지 않으므로 “NO” 반환.

Code

    // Complete the isValid function below.
    static String isValid(String s) {
        Map<Long, Long> chMap = s.chars()
                                 .mapToObj(a -> (char)a)
                                 .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
                                 .entrySet()
                                 .stream()
                                 .map(a -> a.getValue())
                                 .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        
        if(chMap.size() == 1) return "YES";
        else if(chMap.size() > 2) return "NO";
        
        String[] keys = chMap.keySet()
                             .stream()
                             .map(a -> String.valueOf(a))
                             .collect(Collectors.joining(","))
                             .split(",");
        
        long a = Long.parseLong(keys[0]), b = Long.parseLong(keys[1]);  
        if((a == 1 && chMap.get(a) == 1) || (b == 1 && chMap.get(b) == 1)) return "YES"; 
        if(Math.abs(a - b) > 1 || (chMap.get(a) > 1 && chMap.get(b) > 1)) return "NO";
        
        return "YES";
    }