String stack

JavaView on GFG

Intuition

Implement a stack that supports push, pop, and getMin using strings as elements.

Algorithm

1Standard stack with array or linked list backing. String operations same as any stack.

Common Pitfalls

•Standard stack implementation. Push = prepend/append. Pop = remove top. O(1) operations.

String stack.java

Java

// Approach: Stack of characters for push/pop operations; concatenate for peek/display.
// Time: O(1) per op Space: O(n)
class Solution {
    public boolean stringStack(String pat, String tar) {

        int n = pat.length(), m = tar.length();
        int i = n - 1, j = m - 1;

        while (i >= 0 && j >= 0) {
            if (pat.charAt(i) == tar.charAt(j)) {
                j--;
                i--;
            } else
                i -= 2;

            if (j == -1)
                return true;
        }

        return false;
    }
}

Was this solution helpful?