소문자로만 구성된 문자열이 있다고 가정합니다. 모든 문자가 한 번만 나타나도록 모든 중복 문자를 제거해야 합니다. 그리고 우리는 가장 작은 사전 순서로 결과를 표시해야 합니다. 따라서 입력이 "abccb"와 같으면 결과는 "abc"가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ans :=하나의 빈 문자열
-
하나의 스택 정의
-
크기가 26인 onStack 배열 정의
-
하나의 맵 정의
-
n :=s
의 크기 -
i를 초기화하기 위해 :=0, i
-
m[s[i]]를 1 증가
-
-
i를 초기화하기 위해 :=0, i
-
i
크기의 배열 x =s를 정의합니다. -
m[x] 1 감소
-
onStack[x - 'a']가 0이 아니면
-
다음 반복으로 건너뛰고 다음 부분을 무시하십시오.
-
-
st가 비어 있지 않고 x
-
onStack[top of st - 'a'] :=false
-
st에서 항목 삭제
-
-
x를 st에 삽입
-
onStack[x - 'a'] :=참
-
-
(st는 비어 있음) 거짓일 때 −
-
x :=st의 최상위 요소
-
st에서 항목 삭제
-
as =ans + x
-
-
배열 rev
반전 -
반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
string removeDuplicateLetters(string s) {
string ans = "";
stack <char> st;
vector <int> onStack(26);
map <char, int> m;
int n = s.size();
for(int i = 0; i < n; i++){
m[s[i]]++;
}
for(int i = 0; i < n; i++){
char x = s[i];
m[x]--;
if(onStack[x - 'a'])continue;
while(!st.empty() && x < st.top() && m[st.top()]){
onStack[st.top() - 'a'] = false;
st.pop();
}
st.push(x);
onStack[x - 'a'] = true;
}
while(!st.empty()){
char x = st.top();
st.pop();
ans += x;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout << (ob.removeDuplicateLetters("abccb"));
} 입력
“abccb”
출력
“abc”