Problem

Define a string as a “valid bracket string” if it follows the given rules:

“()”, “[]”, and “{}” are all valid bracket strings.
If A is a valid bracket string, then “(A)”, “[A]”, and “{A}” are also valid bracket strings. For example, since “[]” is a valid bracket string, “([])” is also valid.
If A and B are valid bracket strings, then the concatenation “AB” is also a valid bracket string. For example, “{}” and “([])” are valid, so “{}([])” is valid as well.

Given a string s composed of brackets, when the string is rotated left by x positions (0 ≤ x < length of s), determine how many rotations make s a valid bracket string. Return this count.

Constraints

The length of s is between 1 and 1,000.

Example

s	result
“{}”	3
“}]()[{”	2
“[)(]”	0
“}}}”	0

Explanation of Examples

Example 1: “{}”
- Rotating the string in various ways results in different strings. Of these rotations, 3 of them result in a valid bracket string.
Example 2: “}]()[{”
- For this string, rotating it produces various configurations. Only 2 rotations result in a valid bracket string.
Example 3: “[)(]”
- No rotation of this string results in a valid bracket string.
Example 4: “}}}
- No rotation of this string results in a valid bracket string.

Each string needs to be checked for validity after each possible rotation to determine if it becomes a valid bracket string. The function should count how many of these rotated versions are valid and return that count.

How to Approach?

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


import java.util.*;

class Solution {
    public int solution(String s) {
        int count = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (verifyBraket(s)) count++;
            s = rotateBraket(s);
        }
        
        return count;
    }

    private String rotateBraket(String s) {
        // Rotate string by moving first character to the end
        return s.substring(1) + s.charAt(0);
    }
    
    private boolean verifyBraket(String s) {
        Deque<Character> stack = new LinkedList<>();
        
        for (int i = 0; i < s.length(); i++) {
            char current = s.charAt(i);
            
            // Push to stack if opening bracket
            if (current == '(' || current == '[' || current == '{') {
                stack.push(current);
            } else {
                // If stack is empty or brackets do not match, return false
                if (stack.isEmpty()) return false;
                
                char top = stack.peek();
                if ((top == '(' && current == ')') || 
                    (top == '[' && current == ']') || 
                    (top == '{' && current == '}')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        
        // Check if all brackets are matched
        return stack.isEmpty();
    }
}

Java

Algorithms

Stack

Tournament

tuple

Aaron Oh

고려대코딩개발협동조합 창단 멤버

posts