Valid Anagram

https://neetcode.io/problems/is-anagram/question

문자열 s,t가 주어졌을 때 문자 종류와 개수가 완전히 같으면 True
하나라도 다르면 False

문제파악

• 이 문제는 두 문자열이 같은 멀티셋인지 확인하는 문제
  알파벳 소문자로 제한되어 있으므로 크기 26의 배열로 빈도수를
  카운트하고 비교하면 시간복잡도 O(n), 공간복잡도 O(1)로 해결 가능

문제의 핵심

• 소문자 영어 알파벳만 존재
• 길이가 다르면 무조건 False
• 각 문자 등장 횟수가 같아야함
  -> 문자열의 순서는 중요하지 않음. 핵심은 빈도수 비교

사고 흐름

(1) 이 문제의 본질은 두 멀티셋(multiset)이 같은가?
문자열을 그대로 보지 않고 바꿔서 생각해야 함.
s = "racecar" -> {rx2, ax2, cx2, ex1}
t = "carrace" -> {rx2, ax2, cx2, ex1}

멀티셋(multiset) : 중복을 허용하는 집합

(2) 이러한 연산을 잘 지원하는 ADT 떠올리기

• Array : 적합. 고정 알파벳, 인덱싱 기능
• Hash Map : 적합. 일반적인 빈도 카운트
• Set : 부적합. 중복 개수 표현 불가
• Stack / Queue : 부적합. 순서 중요 ADT
• Tree : 부적합. 오버엔지니어링

-> 최적의 ADT는 Array (정수 배열)
알파벳 개수 -> 26개로 고정
문자 -> 인덱스 변환 가능
O(1) 접근, 공간 또한 O(1)

(3) 구현

ADT 구현 입장에서 생각하지 않고 그냥 알고리즘 패턴으로 만 생각할 경우 이 문제는 전형적인 Frequencey Counting Pattern

구현과정

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:

        if len(s) != len(t):
            return False

        alpha = [0] * 26
        length = len(s)

        for i in range(length):
            alpha[ord(s[i])-97] +=1
            alpha[ord(t[i])-97] -=1

        for a in alpha:
            if a != 0:
                return False

        return True
            

문자열을 한 번 순회하므로 O(n), 알파벳 배열 검사나 길이 검사는 O(1). 고로 시간복잡도는 O(n)
공간복잡도는 입력 크기와 무관한 alpha = [0]*26. 고로 공간복잡도는 O(1)

이번에는 길이 체크로직을 위에 넣어서 길이가 다를 경우 early return 과정을 넣었음. 두번 loop를 돌리지 않게 한번만 loop를 돌아서 카운팅하는 것이. 포인트

개선

위 코드에서는 97로 고정했지만 base = ord('a')로 해서 핸들링하면 가독성이 더 좋을 예정.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        
        if len(s) != len(t):
            return False
        
        alpha = [0] * 26
        
        for i in range(len(s)):
            alpha[ord(s[i])-ord('a')] +=1
            alpha[ord(t[i])-ord('a')] -=1
            
        for a in alpha:
            if a !=0:
                return False
        return True

추가

여기서 대소문자가 포함된다거나 Unicode 라던가 스트리밍이라던가 메모리 제한이 심하다면 ?

(1) 대소문자 구분 Anagram
: 두 문자열 s, t가 주어질 때, 문자열은 대소문자(A-Z, a-z)로 구성된다.
대소문자를 구분하여 ('a', 'A')는 다른 문자.
두 문자열이 서로 Anagram이면 true, 아니면 false

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        alpha = [0]*26*2
        
        for i in range(len(s)):
            c1, c2 = s[i], t[i]
            
            if c1.islower():
                alpha[ord(c1)-ord('a')+26]+=1
            else:
                alpha[ord(c1)-ord('A')]+=1
                
            if c2.islower():
                alpha[ord(c2)-ord('a')+26]-=1
            else:
                alpha[ord(c2)-ord('A')]-=1
                
        for a in alpha:
            if a !=0:
                return False
            
        return True

대소문자의 경우에는 소문자 a~z 26개에서 대문자 A~Z로 26개
즉 52개의 제한된 배열로 사용가능
문자 집합의 순서는 중요하지 않고, 중요한 것은 충돌없는 일대일 매핑
기본 소문자에서 대문자로 확장하여 해결.
소문자와 대문자 분기 조건만 확실히 하면 됨.

(2) 유니코드 구분 Anagram

문자열 s,t가 주어질 때, 문자열은 임의의 Unicode 문자를 포함할 수 있다.
(예 : 한글, 일본어, 이모지, 악센트 문자 등)
대소문자 구분 여부는 문제에서 명시된다고 가정할 때, 두 문자열이 Anagram이면 True, 아니면 False

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        cnt = {}
        
        for c1, c2 in zip(s,t):
            cnt[c1] = cnt.get(c1,0)+1
            cnt[c2] = cnt.get(c2,0)-1
            
        return all(v==0 for v in cnt.values())

이 문제는 문자 집합이 사전에 고정되지 않는 멀티셋 비교 문제
유니코드의 문자수를 배열로 하기에는 너무 크거나 대부분 비어있게 됨
인덱스 매핑으로 하기에도 연속적이지 않고 문자 범위 예측 불가
이럴 때는 HashMap / Dictionay ADT 사용

-> Unicode가 포하되면 문자 집합이 고정되지 않기 때문에 배열 대신에 HashMap을 사용했다. 문자열을 한 번 순회하며 빈도수를 대칭적으로 갱신하고, 모든 값이 0인지 확인해서 시간복잡도는 O(n), 공간복잡도는 O(k)
여기서의 k는 서로 다른 문자열의 수
공간복잡도는 더 이상 O(1)이 아님

(3) 스트리밍 Anagram

문자열 s, t가 스트림 형태로 주어지고, 문자 하나씩 순차적으로 도착할 때 전체 문자열을 메모리에 저장할 수 없다. 순서 보장 여부는 문제에 따라 다름. 이 때 두 스트림이 같은 멀티셋인가?

핵심

먼저 생각해야할 것. 두 스트림의 길이를 알 수 있는가?

case 1. 두 스트림의 길이를 알 수 없는 경우 -> 판별 불가
: 끝나는 지점 모름, 중간에 결과 판단 불가, 무한 스트림 가능
스트리밍 환경에서 종료 조건이 명시되지 않으면 anagram 여부를 정확히 판단할 수 없음

case 2. 두 스트림이 같은 길이로 종료됨이 보장됨
: 핵심아이디어는 문자 하나 도착할 때마다 빈도 차이만 유지
s_stream -> +1
t_stream -> -1

ADT의 선택 (스트리밍 + Unicode)

• 알파벳만 : Array
• Unicode : HashMap
• 메모리 제한 : HashMap + pruning

class StreamAnagramChecker:
    def __init__(self):
        self.cnt = {}
        
    def process_s(self,c):
        self.cnt[c] = self.cnt.get(c,0)+1
        if self.cnt[c] == 0:
            del self.cnt[c]
            
    def process_c(self,c):
        self.cnt[c] = self.cnt.get(c,0)-1
        if self.cnt[c] ==0:
            del self.cnt[c]
            
    def is_anagram(self):
        return len(self.cnt) == 0 
       

스트리밍 환경에서는 문자열 전체를 저장할 수 없기 때문에
정렬 기반의 접근은 불가능함. 대신 문자 빈도 차이를 유지하는 HashMap을 사용해서 각 스트림에서 문자가 도착할 때 마다 갱신하고,
종료 시점에 맵이 비어있는지 확인해 anagram 여부를 판단

events = [
    ('s', 'a'),
    ('s', 'b'),
    ('t', 'b'),
    ('s', 'c'),
    ('t', 'a'),
    ('t', 'c'),
]

checker = StreamAnagramChecker()

for source, c in events:
    if source == 's':
        checker.process_s(c)
    else:
        checker.process_c(c)

print(checker.is_anagram())  # True

스트리밍 환경에서는 입력이 이벤트 단위로 들어오기 때문에
각 이벤트가 어느 스트림에서 왔는지를 구분해야함.
따라서 source에 따라 카운트를 증가 또는 감소시키는 분기 필요.

(4) 메모리 제한 문제 Anagram

s,t는 완성된 문자열이고 순서는 무관함. 하지만 메모리의 제한이 있다면?
여기서는 시간은 충분하지만 공간이 문제임
메모리 제한 하에서 anagram은 문자 집합 크기에 따라 전략이 완전히 달라짐.

case1. 문자 집합이 작을 경우(a-z, ASCII 등)
: 고정크기 배열
문자 집합이 제한되어 있다면 고정 배열을 사용하는 것이 메모리 상 최선

case2. 대소문자 포함 (52개)
: 여전히 고정크기 배열

case3. Unicode / 문자집합이 클때
-> 단순 dict ❌. 메모리 O(k). k : 서로 다른 문자 수.
최악의 경우 메모리 O(n)이 될 수 있음.

정확한 판별을 유지하면서 dict보다 메모리를 줄일 수는 없음

정보이론: 서로 다른 문자에 대해 최소 1bit 이상의 정보 필요. 빈도 차이를 기억해야 함. dict는 필요한 만큼만 쓰는 최소 구조

여기서는 반드시 문자 집합의 크기는?, 입력 길이 n의 상한은?, 정확도 100%가 필요한가? 라는 질문으로 해야 최적 해법 정의를 할 수 있음.
메모리 제한이 있는 anagram문제는 어떤 정보까지 저장할 수 있느냐를 먼저 정의해야 함.

H = sum(hash(c) for c in s) - sum(hash(c) for c in t)

메모리 제한이 심한 경우 정확성을 100% 유지하는 것은 불가능하기 때문에
확률적 해시 합 방식을 사용할 수 있음
이는 O(1) 메모리로 동작하지만 충돌 가능성이 있어 false positive를 허용해야 함