Leetcode | 第C节：字符串综合题（2）

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp; // 创建哈希表
        int length = s.length();
        for (auto &ch : s) {
            mp[ch]++; // 枚举每一个字符的出现频率
        }
        vector<pair<char, int>> vec;
        for (auto &it : mp) {
            vec.emplace_back(it); // 将频率放入vector中，这是为了排序，哈希表本身是没有顺序的。
        }
        sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
            return a.second > b.second; // 对量级进行排序
        });
        string ret;
        for (auto &[ch, num] : vec) {
            for (int i = 0; i < num; i++) {
                ret.push_back(ch); // string也可以进行push_back，相当于在后端直接拼接。
            }
        }
        return ret;
    }
};

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> vis(26), num(26);
        for (char ch : s) {
            num[ch - 'a']++; // 记录每一个字符的数量。
        }

        string stk;
        for (char ch : s) {
            if (!vis[ch - 'a']) { // 如果栈中已经存在这个元素，那么无论如何也不能够再入栈
                while (!stk.empty() && stk.back() > ch) {
                    if (num[stk.back() - 'a'] > 0) { // 如果数量为0，不能出栈
                        vis[stk.back() - 'a'] = 0; 
                        stk.pop_back();
                    } else {
                        break;
                    }
                }
                vis[ch - 'a'] = 1; // 标记栈中存在了这个元素
                stk.push_back(ch);
            }
            num[ch - 'a'] -= 1; // 枚举了一个，就要对应字符数量-1
        }
        return stk;
    }
};

public class Solution {
    public int nextGreaterElement(int n) {
        char[] a = ("" + n).toCharArray();
        int i = a.length - 2;
        while (i >= 0 && a[i + 1] <= a[i]) {
            i--; // 从右往左，找到第一个符合条件的位置，这个位置之后的排列都是降序的。
        }
        if (i < 0)
            return -1; // 完全降序，那不可能找到下一个
        int j = a.length - 1;
        while (j >= 0 && a[j] <= a[i]) {
            j--; // 找到第一个“刚刚大一点”的元素，这里注意顺序是从右往左，也是为了考虑到改变后对应数字大小的改变。
        }
        swap(a, i, j);
        reverse(a, i + 1); // 注意，这是自定义的函数，在下面
        try {
            return Integer.parseInt(new String(a));
        } catch (Exception e) {
            return -1; // 注意题目有额外的对于32位数字的要求。
        }
    }
    private void reverse(char[] a, int start) {
        int i = start, j = a.length - 1;
        while (i < j) {
            swap(a, i, j);
            i++;
            j--; // 这是因为一开始的数字一定是降序的，所以这种修改方式可以把它变成升序。当然，你也可以使用排序的api。
        }
    }
    private void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

class Solution {
public:
    int longestSubstring(string s, int k) {
        int ret = 0;
        int n = s.length();
        for (int t = 1; t <= 26; t++) {
            int l = 0, r = 0;
            vector<int> cnt(26, 0);
            int tot = 0;
            int less = 0;
            while (r < n) { // 这一步是为了统计less和tot（对应字符种类个数），同时把r移到最右边
                cnt[s[r] - 'a']++;
                if (cnt[s[r] - 'a'] == 1) {
                    tot++;
                    less++;
                }
                if (cnt[s[r] - 'a'] == k) {
                    less--; // 根据条件更改less
                }

                while (tot > t) { // 更改l的位置
                    cnt[s[l] - 'a']--;
                    if (cnt[s[l] - 'a'] == k - 1) {
                        less++;
                    }
                    if (cnt[s[l] - 'a'] == 0) {
                        tot--;
                        less--;
                    }
                    l++;
                }
                if (less == 0) {
                    ret = max(ret, r - l + 1); // 统计最大的字符串长度
                }
                r++;
            }
        }
        return ret;
    }
};

class Solution {
public:
    string reverseWords(string s) {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;
        for (int start = 0; start < n; ++start) {
            if (s[start] != ' ') {
                // 填一个空白字符然后将idx移动到下一个单词的开头位置
                if (idx != 0) s[idx++] = ' ';

                // 循环遍历至单词的末尾
                int end = start;
                while (end < n && s[end] != ' ') s[idx++] = s[end++];

                // 反转整个单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start，去找下一个单词
                start = end;
            }
        }
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) { // 这是java访问字符串对应位置的api
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
}

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        vector<vector<long>> dp(m + 1, vector<long>(n + 1));
        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }
        for (int i = m - 1; i >= 0; i--) {
            char sChar = s.at(i);
            for (int j = n - 1; j >= 0; j--) {
                char tChar = t.at(j);
                if (sChar == tChar) {
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

class Solution {
public:
    unordered_map <char, int> ori, cnt;

    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        for (const auto &c: t) {
            ++ori[c];
        }

        int l = 0, r = -1;
        int len = INT_MAX, ansL = -1, ansR = -1;

        while (r < int(s.size())) {
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                }
                if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
                }
                ++l;
            }
        }

        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};