Welcome to Subscribe On Youtube

3039. Apply Operations to Make String Empty

Description

You are given a string s.

Consider performing the following operation until s becomes empty:

  • For every alphabet character from 'a' to 'z', remove the first occurrence of that character in s (if it exists).

For example, let initially s = "aabcbbca". We do the following operations:

  • Remove the underlined characters s = "aabcbbca". The resulting string is s = "abbca".
  • Remove the underlined characters s = "abbca". The resulting string is s = "ba".
  • Remove the underlined characters s = "ba". The resulting string is s = "".

Return the value of the string s right before applying the last operation. In the example above, answer is "ba".

 

Example 1:

 Input: s = "aabcbbca" Output: "ba" Explanation: Explained in the statement.

Example 2:

 Input: s = "abcd" Output: "abcd" Explanation: We do the following operation: - Remove the underlined characters s = "abcd". The resulting string is s = "". The string just before the last operation is "abcd".

 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists only of lowercase English letters.

Solutions

Solution 1

  • class Solution { public String lastNonEmptyString(String s) { int[] cnt = new int[26]; int[] last = new int[26]; int n = s.length(); int mx = 0; for (int i = 0; i < n; ++i) { int c = s.charAt(i) - 'a'; mx = Math.max(mx, ++cnt[c]); last[c] = i; } StringBuilder ans = new StringBuilder(); for (int i = 0; i < n; ++i) { int c = s.charAt(i) - 'a'; if (cnt[c] == mx && last[c] == i) { ans.append(s.charAt(i)); } } return ans.toString(); } } 
  • class Solution { public: string lastNonEmptyString(string s) { int cnt[26]{}; int last[26]{}; int n = s.size(); int mx = 0; for (int i = 0; i < n; ++i) { int c = s[i] - 'a'; mx = max(mx, ++cnt[c]); last[c] = i; } string ans; for (int i = 0; i < n; ++i) { int c = s[i] - 'a'; if (cnt[c] == mx && last[c] == i) { ans.push_back(s[i]); } } return ans; } }; 
  • class Solution: def lastNonEmptyString(self, s: str) -> str: cnt = Counter(s) mx = cnt.most_common(1)[0][1] last = {c: i for i, c in enumerate(s)} return "".join(c for i, c in enumerate(s) if cnt[c] == mx and last[c] == i) 
  • func lastNonEmptyString(s string) string { cnt := [26]int{} last := [26]int{} mx := 0 for i, c := range s { c -= 'a' cnt[c]++ last[c] = i mx = max(mx, cnt[c]) } ans := []rune{} for i, c := range s { if cnt[c-'a'] == mx && last[c-'a'] == i { ans = append(ans, c) } } return string(ans) } 
  • function lastNonEmptyString(s: string): string { const cnt: number[] = Array(26).fill(0); const last: number[] = Array(26).fill(0); const n = s.length; let mx = 0; for (let i = 0; i < n; ++i) { const c = s.charCodeAt(i) - 97; mx = Math.max(mx, ++cnt[c]); last[c] = i; } const ans: string[] = []; for (let i = 0; i < n; ++i) { const c = s.charCodeAt(i) - 97; if (cnt[c] === mx && last[c] === i) { ans.push(String.fromCharCode(c + 97)); } } return ans.join(''); }

All Problems

All Solutions