LeetCode in Kotlin

3039. Apply Operations to Make String Empty

Medium

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 = "**a**a**bc**bbca". The resulting string is s = "abbca".
• Remove the underlined characters s = "**ab**b**c**a". 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.

Solution

import kotlin.math.max

class Solution {
    fun lastNonEmptyString(s: String): String {
        val freq = IntArray(26)
        val ar = s.toCharArray()
        val n = ar.size
        var max = 1
        val sb = StringBuilder()
        for (c in ar) {
            freq[c.code - 'a'.code]++
            max = max(freq[c.code - 'a'.code], max)
        }
        for (i in n - 1 downTo 0) {
            if (freq[ar[i].code - 'a'.code] == max) {
                sb.append(ar[i])
                freq[ar[i].code - 'a'.code] = 0
            }
        }
        return sb.reverse().toString()
    }
}

This site is open source. Improve this page.