scoyer_result(C++)


  • 0
    H

    Firstly, We find the first position of the 'last' character, for example, the first position of “aabac” is 2 (index starts from 0), “ababv” ' s result is 2 too.

    Secondly, we find the minimum letter c from the beginning to the position we find in the first step, and mark the position as min_pos.

    Thirdly, we delete the c from the min_pos + 1 to the end, add the result c, the remaining string is ns.

    Lastly, pass the new string ns for doing the step1~3 recursively.

    Why does the algorithm works?
    The reason why we find the 'last position' in the first step is that you must choose a letter from the beginning to the 'last position'. In greedy algorithm, we have better choose the optimal letter during this segment. So the algorithm works.

    My Code:

    class Solution {
    public:
        string removeDuplicateLetters(string s) {
    		if (s.empty()) {
    			return s;
    		}
    		vector<int> cnt(26, 0);
    		int n = s.length();
    		for (int i = 0; i < n; i++) {
    			cnt[s[i] - 'a']++;
    		}
    		int min_pos = 0;
    		for (int i = 0; i < n; i++) {
    			if (s[min_pos] > s[i]) min_pos = i;
    			if (!--cnt[s[i] - 'a']) break;
    		}
    		string ns;
    		for (int i = min_pos + 1; i < n; i++) {
    			if (s[i] == s[min_pos]) continue;
    			ns.push_back(s[i]);
    		}
    		string ret;
    		ret.push_back(s[min_pos]);
    		return ret + removeDuplicateLetters(ns);
        }
    };
    

  • 0
    B

    Thanks for sharing this alternate greedy method.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.