1648.最大サブストリング
8306 ワード
与えられた文字列sは、sの最後のサブ文字列を辞書順に返す.
例1:
入力:「abab」出力:「bab」解釈:sのサブストリングは["a","ab","aba","abab","b","ba","bab"].ここで、辞書順の最後のサブ列は「bab」である.例2:
入力:baca出力:ca注意1<=s.length<=4*10^4 s小文字のみを含む.
例1:
入力:「abab」出力:「bab」解釈:sのサブストリングは["a","ab","aba","abab","b","ba","bab"].ここで、辞書順の最後のサブ列は「bab」である.例2:
入力:baca出力:ca注意1<=s.length<=4*10^4 s小文字のみを含む.
class Solution {
public:
/**
* @param s: the matrix
* @return: the last substring of s in lexicographical order
*/
/*
:
//
,
*/
vector<int>max_index; //
void findMaxIndex(string s, string max) // s max max_index
{
if (s == "")
return;
string::size_type pos = s.find(max);
if (pos == string::npos)
return;
else
{
max_index.push_back(pos);
}
string newSub = s.replace(s.begin() + pos, s.begin() + pos + 1, "a");
findMaxIndex(newSub, max);
}
string maxSubstring(string &s) {
// Write your code here.
if (s == "")
return NULL;
string lastStr;
string::iterator it = max_element(s.begin(), s.end());
string max;
max=*it;
findMaxIndex(s, max);
vector<string>res;// ,
for (int i = 0; i < max_index.size(); i++)
{
int pos = max_index[i];
string tmp = s.substr(pos,s.length()-pos );
res.push_back(tmp);
}
sort(res.begin(), res.end());
lastStr = res[res.size()-1];
return lastStr;
}
};