Given two strings, find the number of common characters between them.

Example

For s1 = "aabcc" and s2 = "adcaa", the output should be

solution(s1, s2) = 3.

Strings have 3 common characters - 2 "a"s and 1 "c".

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] string s1

  A string consisting of lowercase English letters.

  Guaranteed constraints:

  1 ≤ s1.length < 15.

• [input] string s2

  A string consisting of lowercase English letters.

  Guaranteed constraints:

  1 ≤ s2.length < 15.

• [output] integer

풀이

• 자료구조의 특징을 이용해 무난하게 해결 가능

int solution(String s1, String s2) {
    // 누적합 선언
    int result = 0;
    // 문자열 파라미터 char Array 로 변경
    char [] arr1 = s1.toCharArray();
    char [] arr2 = s2.toCharArray();
    // 각 문자열의 요소들과 요소들의 갯수 담는 자료구조
    HashMap <Character, Integer> map1 = new HashMap<>();
    HashMap <Character, Integer> map2 = new HashMap<>();
    // 두 문자열의 요소들을 중복없이 담기위한 자료구조
    HashSet <Character> set = new HashSet <Character>();
    
    // 각 문자열을 순회하면서
    // set 과 map 에 카운팅
    for (int i = 0; i < arr1.length; i ++) {
        char c = arr1[i];
        set.add(c);
        map1.put(c, map1.getOrDefault(c, 0) + 1);
    }
    
    for (int i = 0; i < arr2.length; i ++) {
        char c = arr2[i];
        set.add(c);
        map2.put(c, map2.getOrDefault(c, 0) + 1);
    }
    
    // 모든 문자열에 대해 순회
    for (char c : set) {
        // 1, 2 번째 문자열에 모두 속할 경우
        if (map1.containsKey(c) && map2.containsKey(c)) {
            // 각 문자열에서 나온 동일 요소의 횟수 중 작은 것을 누적한다.
            result += Math.min(map1.get(c), map2.get(c));
        }
    }
    
    return result;
}