2520. Using A Robot To Print The Lexicographically Smallest String¶

LeetCode Problem View on GitHub

2520. Using a Robot to Print the Lexicographically Smallest String

Medium

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.

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 <= 105
• s consists of only English lowercase letters.

Solution¶

class Solution {
    public String robotWithString(String s) {
        int n = s.length();
        int freq[] = new int[26];
        Stack<Integer> st = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) freq[s.charAt(i) - 'a']++;
        for (int i = 0; i < n; i++) {
            int ch = s.charAt(i) - 'a';
            if (check(ch - 1, freq)) {
                st.add(ch);
                freq[ch]--;
            }
            else {
                sb.append((char)(ch + 'a'));
                freq[ch]--;
                while (st.size() > 0 && !check(st.peek() - 1, freq)) {
                    sb.append((char)(st.pop() + 'a'));
                }
            }
        }
        while (st.size() > 0) sb.append((char)(st.pop() + 'a'));
        return sb.toString();
    }
    private boolean check(int ch, int freq[]) {
        for (int i = 0; i <= ch; i++) if (freq[i] > 0) return true;
        return false;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here