Problem

Given a string of length 2N containing N ‘S’ characters (indicating push operations) and N ‘X’ characters (indicating pop operations), you need to check if the operation sequence is admissible. A string of operations is admissible if it abides by the properties of a stack, meaning that you cannot pop from an empty stack. Thus, at any point, the number of ‘S’s encountered must be greater than or equal to the number of ‘X’s.

Examples

Example 1:

Input: "SSXX"
Output: True
Explanation: The operations are valid. First push twice, then pop twice. The stack never becomes negative.

Example 2:

Input: "XSXS"
Output: False
Explanation: The operations attempt to pop before a push, which is invalid.

Solution

Method 1 - Using counter

Here is the approach:

  1. Initialise a counter to keep track of the difference between the number of ‘S’s and ‘X’s.
  2. Traverse the string character by character.
  3. Increment the counter for ‘S’ and decrement it for ‘X’.
  4. At any step, if the counter becomes negative, return false (indicating the sequence is not permissible).
  5. After traversing the entire string, if the counter is non-negative and equals zero, return true.

Code

Java
public class Solution {
    public boolean isAdmissible(String operations) {
        int counter = 0;
        for (char operation : operations.toCharArray()) {
            if (operation == 'S') {
                counter += 1;
            } else if (operation == 'X') {
                counter -= 1;
            }
            if (counter < 0) {
                return false;
            }
        }
        return counter == 0;
    }

    // Examples usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isAdmissible("SSXX"));  // True
        System.out.println(solution.isAdmissible("XSXS"));  // False
    }
}
Python
class Solution:
    def is_admissible(self, operations: str) -> bool:
        counter = 0
        for operation in operations:
            if operation == 'S':
                counter += 1
            elif operation == 'X':
                counter -= 1
            if counter < 0:
                return False
        return counter == 0

# Examples usage
solution = Solution()
print(solution.is_admissible("SSXX"))  # True
print(solution.is_admissible("XSXS"))  # False

Complexity

  • ⏰ Time complexity:  O(n) because we only traverse the string once.
  • 🧺 Space complexity: O(1) because we only use a constant amount of additional space.