3039. Apply Operations to Make String Empty LeetCode Solution

In this guide, you will get 3039. Apply Operations to Make String Empty LeetCode Solution with the best time and space complexity. The solution to Apply Operations to Make String Empty problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Apply Operations to Make String Empty solution in C++
  4. Apply Operations to Make String Empty solution in Java
  5. Apply Operations to Make String Empty solution in Python
  6. Additional Resources
3039. Apply Operations to Make String Empty LeetCode Solution image

Problem Statement of Apply Operations to Make String Empty

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”.

See also  2423. Remove Letter To Equalize Frequency LeetCode Solution

Constraints:

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(26) = O(1)

3039. Apply Operations to Make String Empty LeetCode Solution in C++

class Solution {
 public:
  string lastNonEmptyString(string s) {
    string ans;
    vector<int> count(26);

    for (const char c : s)
      ++count[c - 'a'];

    const int maxFreq = ranges::max(count);

    for (int i = s.length() - 1; i >= 0; --i)
      if (count[s[i] - 'a']-- == maxFreq)
        ans += s[i];

    ranges::reverse(ans);
    return ans;
  }
};
/* code provided by PROGIEZ */

3039. Apply Operations to Make String Empty LeetCode Solution in Java

class Solution {
  public String lastNonEmptyString(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];

    for (final char c : s.toCharArray())
      ++count[c - 'a'];

    final int maxFreq = Arrays.stream(count).max().getAsInt();

    for (int i = s.length() - 1; i >= 0; --i)
      if (count[s.charAt(i) - 'a']-- == maxFreq)
        sb.append(s.charAt(i));

    return sb.reverse().toString();
  }
}
// code provided by PROGIEZ

3039. Apply Operations to Make String Empty LeetCode Solution in Python

class Solution:
  def lastNonEmptyString(self, s: str) -> str:
    ans = []
    count = collections.Counter(s)
    maxFreq = max(count.values())

    for c in reversed(s):
      if count[c] == maxFreq:
        ans.append(c)
        count[c] -= 1

    return ''.join(reversed(ans))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: