1

# 一、在字串中找出subsequence中包含相異字母字典排序最小的

316題說，去除重複的字，使剩下的答案為字典排序最小
1081題說找出subsequence中包含相異字母字典排序最小的，
(假設input全由小寫字母組成)

## python解

``````class Solution:
def smallestSubsequence(self, text: str) -> str:
ans = []
for i,c in enumerate(text):
if c not in ans:
while ans and c < ans[-1] and ans[-1] in text[i+1:]:
ans.pop()
ans.append(c)
return ''.join(ans)
``````

## c++解

``````class Solution {
public:
string smallestSubsequence(string s) {
unordered_map<char, int> count; //記錄每個字元出現幾次，幫助判斷舊的字元是否在後面有出現
string res;
for (auto c : s){
count[c]++;
}
for (auto c : s) {
count[c]--;
if (res.find(c)==string::npos){
while (!res.empty() && c < res.back() && count[res.back()]>0){
res.pop_back();
}
res.push_back(c);
}
}
return res;
}
};
``````

# 二、回傳字串s中，字典序最大的子字串

python的解單純拿suffix來比大小可以過關(但耗時)

## python解，AC(760ms)

``````class Solution:
def lastSubstring(self, s: str) -> str:
return max(s[idx:] for idx in range(len(s)))
``````

## c++解，TLE

``````class Solution {
public:
string lastSubstring(string s) {
string res(s);
for(int i=1; i<s.size();i++){
string t(s.begin()+i, s.end());
if(t>res){
res = t;
}
}
return res;
}
};
``````

## c++解，AC(108ms)

``````class Solution {
public:
string lastSubstring(string s) {
int n=s.size(),i=0,j=1,k=0;
while(j+k<n)
{
if(s[i+k]<s[j+k]){
i = j++;
k = 0;
}
else if(s[i+k]>s[j+k]){
j += k+1;
k = 0;
}
else{
k++;
}
}
return string(s.begin()+i, s.end());
}
};
``````

# 自我練習- 找字串中字典序最大的subsequence

(就好像說找兩個正整數的「最小公因數」，答案一定是1，太過簡單)

(沒有找到對應的題目做，希望思路是對的)

``````def lastSubseq(s: str) -> str:
ans = []
for i,c in enumerate(s):
while ans and c > ans[-1]:
ans.pop()
ans.append(c)
return ''.join(ans)
``````