2434. Using a Robot to Print the Lexicographically Smallest String

class Solution {
    public String robotWithString(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>(); //t
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            stack.push(c);
            freq[c - 'a']--;
            while (!stack.isEmpty() && stack.peek() <= findSmallet(freq)) { // remian freq larger than stack top, is the ans (from t end)
                char pop = stack.pop();
                result.append(pop);
            }
        }
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.toString();
    }

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


/*
op1, op2 can interact to use

use Stack idea to pop, push

T: O(n)
S: O(n)

*/

record the current smallest index (not very different)

class Solution {
    private int currentSmallestIndex = 0;
    public String robotWithString(String s) {
        ArrayDeque<Character> stack = new ArrayDeque<>(); //t
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            stack.push(c);
            freq[c - 'a']--;
            while (!stack.isEmpty() && stack.peek() <= findSmallet(freq)) { // remian freq larger than stack top, is the ans (from t end)
                char pop = stack.pop();
                result.append(pop);
            }
        }
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.toString();
    }

    private char findSmallet(int[] freq) {
        for (int i = currentSmallestIndex; i < 26; i++) {
            if (freq[i] != 0) {
                currentSmallestIndex = i;
                return (char)(i + 'a');
            }
        }
        return 'a';
    }
}


/*
op1, op2 can interact to use

use Stack idea to pop, push

T: O(n)
S: O(n)

*/