Yahoo

01Modify the String

Given a string input_str of length n, choose any character that occurs at least twice and delete any one occurrence. Repeat this until all remaining characters are distinct. Return the lexicographically maximum string that can be formed this way. Function Description Complete the function getString in the editor below. getString has the following parameters:

string input_str: a string of length n Returns string: the result of the operations, as described

Constraints

input_str contains only lowercase English letters
1 ≤ n ≤ 10⁵

Example 1

Input:

input_str = "aabcb"

Output:

"acb"

Explanation: The length of the string, n = 5. Some of the strings that can be formed are:

"acb" - delete the first occurrences of 'a' and 'b'
"abc" - delete the first occurrence of 'a' and the second occurrence of 'b' It can be proven that the lexicographically maximum string that can be obtained is "acb".

解法

字典序最大且字符全部互不相同 ⇒ 单调栈贪心。维护栈和 in_stack 集合 + 剩余字符计数。遍历字符 c：若已在栈内则该字符剩余计数 - 1 后跳过；否则在栈顶字符 t < c 且 t 还会在后面出现时弹出 t，最后入栈。复杂度 O(n)，空间 O(σ)。

from collections import Counter

def get_string(input_str: str) -> str:
    remain = Counter(input_str)
    in_stk = set()
    stk = []
    for c in input_str:
        if c in in_stk:
            remain[c] -= 1
            continue
        while stk and stk[-1] < c and remain[stk[-1]] > 1:
            top = stk.pop()
            in_stk.remove(top)
            remain[top] -= 1
        stk.append(c)
        in_stk.add(c)
    return "".join(stk)

class Solution {
    String getString(String inputStr) {
        int[] remain = new int[26];
        for (char c : inputStr.toCharArray()) remain[c - 'a']++;
        boolean[] inStk = new boolean[26];
        StringBuilder stk = new StringBuilder();
        for (char c : inputStr.toCharArray()) {
            if (inStk[c - 'a']) { remain[c - 'a']--; continue; }
            while (stk.length() > 0 && stk.charAt(stk.length() - 1) < c
                   && remain[stk.charAt(stk.length() - 1) - 'a'] > 1) {
                char top = stk.charAt(stk.length() - 1);
                stk.deleteCharAt(stk.length() - 1);
                inStk[top - 'a'] = false;
                remain[top - 'a']--;
            }
            stk.append(c);
            inStk[c - 'a'] = true;
        }
        return stk.toString();
    }
}

class Solution {
public:
    string getString(string inputStr) {
        int remain[26] = {0};
        for (char c : inputStr) remain[c - 'a']++;
        bool inStk[26] = {false};
        string stk;
        for (char c : inputStr) {
            if (inStk[c - 'a']) { remain[c - 'a']--; continue; }
            while (!stk.empty() && stk.back() < c && remain[stk.back() - 'a'] > 1) {
                char top = stk.back();
                stk.pop_back();
                inStk[top - 'a'] = false;
                remain[top - 'a']--;
            }
            stk.push_back(c);
            inStk[c - 'a'] = true;
        }
        return stk;
    }
};

02Count Binary Substrings

A binary string is a string consisting only of 0s and 1s. A substring is a contiguous group of characters within a string. Given a binary string, find the number of substrings that contain an equal number of 0s and 1s and all the 0s and 1s are grouped together. Note that duplicate substrings are also counted in the answer. For example, '0011' has two overlapping substrings that meet the criteria: '0011' and '01'. Function Description Complete the function getSubstringCount in the editor. getSubstringCount has the following parameter(s):

s: String: a binary string Returns int: the number of substrings that meet the criteria

Constraints

1 ≤ length of s ≤ 10⁵
The string s consists of 0s and 1s only.

Example 1

Input:

s = "011001"

Output:

Explanation: The substrings "01", "10", "1100", and "01" have equal numbers of 0s and 1s with all 0s and 1s grouped consecutively. Hence, the answer is 4. Note that the substring "0110" has an equal number of 0s and 1s but is not counted because not all 0s and 1s are grouped together.

解法

等价于 LeetCode 696。把字符串压缩成连续等字符段长度数组 groups，相邻两段贡献 min(groups[i], groups[i+1]) 个合法子串。复杂度 O(n)，空间 O(1)(流式计算前段长度即可)。

def get_substring_count(s: str) -> int:
    prev, cur = 0, 1
    ans = 0
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            cur += 1
        else:
            ans += min(prev, cur)
            prev, cur = cur, 1
    ans += min(prev, cur)
    return ans

class Solution {
    int getSubstringCount(String s) {
        int prev = 0, cur = 1, ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) cur++;
            else { ans += Math.min(prev, cur); prev = cur; cur = 1; }
        }
        ans += Math.min(prev, cur);
        return ans;
    }
}

class Solution {
public:
    int getSubstringCount(string s) {
        int prev = 0, cur = 1, ans = 0;
        for (size_t i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) ++cur;
            else { ans += min(prev, cur); prev = cur; cur = 1; }
        }
        ans += min(prev, cur);
        return ans;
    }
};