class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size()-1; i < j; i++, j--){
            char tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += 2*k){
            if(i+k-1 < s.size()-1){
                reverse(s.begin()+i, s.begin()+i+k);
            }
            else{
                reverse(s.begin()+i, s.end());
            }
        }
        return s;
    }
};

class Solution {
public:
    string replaceSpace(string s) {
        int oldSize = s.size();
        int count = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == ' ') count++;
        }
        s.resize(oldSize + 2*count);
        int newSize = s.size();
        for(int i = oldSize-1, j = newSize-1; i < j; i--, j--){
            if(s[i] != ' ') s[j] = s[i];
            else{
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -= 2;
            }
        }
        return s;
    }
};

class Solution {
public:
    void removeExtraSpaces(string& s){
        int slowIndex=0;
        for (int i=0; i<s.size(); i++){
            if (s[i]!=' '){
                if (slowIndex != 0) s[slowIndex++] = ' '; //單詞之間用空格分隔,slow如果是在句首那就不用加了
                while(s[i] != ' ' && i < s.size()){
                    s[slowIndex++] = s[i++];
                }
            }
        }
        s.resize(slowIndex);
    }
    void reverseString(string& s, int start, int end){
        for (int i=start, j=end; i<j; i++,j--){
            swap(s[i],s[j]);
        }
    }
    string reverseWords(string s) {
        //1.去除前導
        //2.去除中間多余一個的空格
        //3.去除結尾空格
        //erase函數的時間復雜度為O(n),所以如果遍歷整個字符串進行erase時間復雜度會增加到O(n方)
        //先將整個字符串reverse一遍，再按單詞為單位進行reverse，這樣可以獲得最好的時間復雜度
        removeExtraSpaces(s);
        reverseString(s, 0, s.size()-1);
        int start = 0;
        for (int i=0; i<=s.size(); i++){ //需要<=,因為reverse是按照i-1
            if (s[i] == ' ' || i == s.size()){
                reverseString(s, start, i-1);
                start = i+1;
            }
        }
        return s;
    }
};