[C++] Interview Question : Find duplicate characters

Question

문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하라. 

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  모든 문자열의 문자를 살펴보아야 하므로 문자열의 길이를 s이라 하였을 때 BCR은 O(s)이다.

 

고려사항

1. 문자열이 ASCII 인지 유니코드인지
2. ASCII인 경우 최대 몇개의 문자의 개수를 몇개로 가정할 것인지

---

Solution 1 (Bruth Force)

문자 하나를 기준으로, 다른 문자가 같은지 탐색한다. 시간복잡도는 O(s^2)이다.

bool solution(string s) {
	for(int i=0; i<s.length(); i++){
	    for(int j=i+1; j<s.length(); j++){
	        if(s[i] == s[j]) return true;
	    }
	}
	return false;
}

• Time complexity : O(s^2)
• Space complexity : O(1) 

---

Solution 2 (Hash 사용)

문자 하나를 기준으로, 다른 문자가 다시 등장하는지 여부만 파악하면 되기 때문에 hash를 사용할 수 있다. 시간 복잡도는 O(s)이다

bool solution(string s) {
    set<char> my_set;
    for(int i=0; i<s.length(); i++){
        if(my_set.find(s[i]) != my_set.end()) return true;
        my_set.insert(s[i]);
    }
    
    return false;
}

• Time complexity : O(s)
• Space complexity : O(1) 

---

Solution 3 (Hash대신 배열 사용)

만약 면접관과 등장할 수 있는 문자를 ASCII로 제한 했다면, 128개 이하로 표현을 할 수 있다. 이를 안다면 굳이 자료구조를 쓰지 않고 배열을 사용할 수 있다. 

bool solution(string s) {
    int count[128] = { 0 };
    
    for(int i = 0; i<s.length();i++){
        if(count[s[i]] != 0) return true;
        count[s[i]]++;
    }
    
    return false;
}

• Time complexity : O(s)
• Space complexity : O(1) 

Solution 4 (int 변수 하나로 저장)

위와 마찬가지로 만약 등장할 수 있는 문자를 영어 소문자 혹은 대문자로만 제한했다면, int 변수 하나로 문제를 해결할 수 있다.

bool solution(string s) {
	int mark = 0;
    for(int i = 0; i<s.length();i++){
    	if(((mark >> s[i] - 'a') & 1) == 1) return true;
        mark |= (1 << s[i] -'a');
    }
    
    return false;
}

• Time complexity : O(s)
• Space complexity : O(1)