leetcode 316. Remove Duplicate Letters

梦里梦外; 2022-08-20 11:29 139阅读 0赞

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.  
  
  
Example:  
Given "bcabc"  
Return "abc"  
  
  
Given "cbacdcbc"

Return "acdb"

// ConsoleApplication4.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>  
    #include<map>  
    #include<iterator>  
    #include<algorithm>  
    #include<iostream>  
    using namespace std;
    
    class Solution {
    public:
    	char do_once(string&str, map<char, int>count)
    	{
    		int i = 0;
    		string s = str;
    		if (s.size() == 1)
    			return s[0];
    		for (i = 0; i < s.length(); i++)
    			if (count[s[i]] == 1)
    				break;
    		if (i == 0)
    		{
    			char ret = s[0];
    			s.erase(0, 1);
    			str = s;
    			return ret;
    		}
    		map<char, int>count1;
    		vector<char>p;
    		for (int j = 0; j < i; j++)
    			count1[s[j]]++;
    		for (map<char, int>::iterator it = count1.begin(); it != count1.end(); it++)
    		{
    			if (it->second == count[it->first])
    				p.push_back(it->first);
    		}
    		if (p.size()>0)
    		{
    			sort(p.begin(), p.end());//从小到大排序
    			int gg = -1;
    			bool flag = false;
    			for (int j = 0; j < p.size(); j++)
    			{
    				flag = false;
    				for (int q = 0; q < i; q++)
    					if (s[q] == p[j])
    					{
    						gg = q;
    						break;
    					}
    				map<char, int>count2;
    				for (int qq = 0; qq < gg; qq++)
    					count2[s[qq]]++;
    				for (map<char, int>::iterator it1 = count2.begin(); it1 != count2.end(); it1++)
    					if (it1->second == count[it1->first])
    					{
    						flag = true;
    						break;
    					}
    				if (!flag)
    					break;
    			}
    			if (!flag)
    			{
    				char ret = s[gg];
    				int jj = i;
    				for (jj = i; jj >= 0; jj--)
    					if (s[jj] == ret)
    						break;
    				vector<char>iu;
    				for (int j = 0; j < jj; j++)
    				{
    					if (s[j] < ret&&find(p.begin(), p.end(), s[j])
    						== p.end() && find(iu.begin(), iu.end(), s[j]) == iu.end())
    						iu.push_back(s[j]);
    					//cout << 1 << endl;
    				}
    				if (iu.size() > 0)
    				{
    					sort(iu.begin(), iu.end());
    					int jjj = -1;
    					for (jjj = 0; jjj < jj; jjj++)
    						if (s[jjj] == iu[0])
    							break;
    					ret = iu[0];
    					jj = jjj;
    					gg = jj;
    				}
    				s.erase(s.begin(), s.begin() + gg + 1);
    				while (s.find(ret) != string::npos)
    				{
    					s.erase(s.find_first_of(ret), 1);
    				}
    				str = s;
    				return ret;
    			}
    			else
    			{
    				int q;
    				for (q = 0; q < i; q++)
    					if (s[q] == p[0])
    						break;
    				if (i < s.length() && s[i] < p[0])
    				{
    					char ret = s[i];
    					s.erase(s.begin(), s.begin() + i + 1);
    					while (s.find(ret) != string::npos)
    					{
    						s.erase(s.find_first_of(ret, 1));
    					}
    					str = s;
    					return ret;
    				}
    				else
    				{
    					s.erase(s.begin(), s.begin() + q + 1);
    					while (s.find(p[0]) != string::npos)
    					{
    						s.erase(s.find_first_of(p[0]), 1);
    					}
    					str = s;
    					return p[0];
    				}
    			}
    		}
    		else
    		{
    			vector<char>pp;
    			vector<int>th;
    			for (int d = 0; d <= i; d++)//此时i<s.length()
    				if (find(pp.begin(), pp.end(), s[d]) == pp.end())
    				{
    					pp.push_back(s[d]);
    					th.push_back(d);
    				}
    			char min = 127;
    			int th1 = -1;
    			for (int j = 0; j < pp.size(); j++)
    				if (pp[j] < min)
    				{
    					min = pp[j];
    					th1 = th[j];
    				}
    			s.erase(s.begin(), s.begin() + th1 + 1);
    			while (s.find(min) != string::npos)
    			{
    				s.erase(s.find_first_of(min), 1);
    			}
    			str = s;
    			return min;
    		}
    	}
    
    	string removeDuplicateLetters(string s) {
    		map<char, int>count;
    		string re;
    		string str = s;
    		for (int i = 0; i < str.length(); i++)
    			count[str[i]]++;
    		int k = count.size();
    		while (k > 0)
    		{
    			count.clear();
    			for (int i = 0; i < str.length(); i++)
    				count[str[i]]++;
    			re.push_back(do_once(str, count));
    			k--;
    		}
    
    		return re;
    	}
    };
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    
    
    	Solution sl;
    	//cout << sl.removeDuplicateLetters("rusrbofeggbbkyuyjsrzornpdguwzizqszpbicdquakqws").c_str();
    	//"bfegkuyjorndiqszpcaw"
    	cout << sl.removeDuplicateLetters("peymrzknlxtrutjiybqemquchgvtmmtpjvunvekszrkatctcirxwuqknrycpdtcuadblzkkleduezgspoxhhssoipbmdgrqggpfdsanolzczpaggwxrlaleaqtnzxclmxwjucnujsptnbmmjzzjhypnlsoxjveywsufegzlfnyvkcnfevkshbckfropoydkdlblppllgefagjgpajsplvxknvtlgtjyhmnwxcpjjzcizihycvsnhnnmqohivekitxzuo").c_str();
    	system("pause");
    	return 0;
    }

acceped