1648.最大サブストリング


与えられた文字列sは、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;
	}


};