Leetcode 2434 : Using a Robot to Print the Lexicographically Smallest String

Problem Statement

You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:

Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
Remove the last character of a string t and give it to the robot. The robot will write this character on paper.
Return the lexicographically smallest string that can be written on the paper.

Input

Example 1:

Input: s = "zza"
Output: "azz"
Explanation: Let p denote the written string.
Initially p="", s="zza", t="".
Perform first operation three times p="", s="", t="zza".
Perform second operation three times p="azz", s="", t="".
Example 2:

Input: s = "bac"
Output: "abc"
Explanation: Let p denote the written string.
Perform first operation twice p="", s="c", t="ba".
Perform second operation twice p="ab", s="c", t="".
Perform first operation p="ab", s="", t="c".
Perform second operation p="abc", s="", t="".
Example 3:

Input: s = "bdda"
Output: "addb"
Explanation: Let p denote the written string.
Initially p="", s="bdda", t="".
Perform first operation four times p="", s="", t="bdda".
Perform second operation four times p="addb", s="", t="".

Constraints

1 <= s.length <= 10^5
s consists of only English lowercase letters.

Intuition

It is always better to remove the smaller string from the end of the string and then write it on paper. We can use a stack and a frequency array to see whether the character is the smallest character by just checking whether the frequency map has a value greater than 0.

Approach

• Calculate the frequencies of the character in the array of 26.
• Push the characters into the stack, reduce the frequency, and pop the lexicographically smallest character.
• Store the remaining characters from the stack into the final result.

Complexity

• Time complexity:

  O(lengthOfString) + O(lengthOfString)

• Space complexity:

  O(lengthOfString) + O(26)

Code

class Solution {
    public String robotWithString(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        StringBuilder result = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        int [] freq = new int [26];
        for (char ch : s.toCharArray()) {
            freq[ch - 'a']++;
        }
        for (char ch : s.toCharArray()) {
            stack.push(ch);
            freq[ch - 'a']--;
            while (!stack.isEmpty() && stack.peek() <= smallestChar(freq)) {
                char topChar = stack.pop();
                result.append(topChar);
            }
        }
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.toString();
    }

    private char smallestChar(int [] freq) {
        for (int index = 0; index < 26; index++) {
            if (freq[index] != 0) {
                return (char)(index + 'a');
            }
        }
        return 'z';
    }
}