Your browser is not supported. Please, update your browser or switch to a different one. Learn more about which browsers are supported.
Tasks Details
easy
1.
Brackets
Determine whether a given string of parentheses (multiple types) is properly nested.
Task Score
100%
Correctness
100%
Performance
100%
Task description
A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
- S is empty;
- S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
- S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
class Solution { public int solution(String S); }
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..200,000];
- string S is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 22 minutes
Notes
not defined yet
Task timeline
Code: 10:04:59 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return 1;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:5: error: ';' expected
public static final int BALANCED = 1
^
1 error
Code: 10:05:15 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:36: error: wrong number of type arguments; required 2
private Map<Character> language = new HashMap<>(){{
^
Solution.java:52: error: cannot find symbol
public List<T> stack;
^
symbol: class List
location: class Stack<T>
where T is a type-variable:
T extends Object declared in class Stack
Solution.java:9: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
Solution.java:11: error: cannot infer type arguments for Stack<>
Stack<Character> stack = new Stack<>();
^
reason: cannot infer type-variable(s) T
(actual and formal argument lists differ in length)
where T is a type-variable:
T extends Object declared in class Stack
Solution.java:36: error: cannot infer type arguments for HashMap<K,V>
private Map<Character> language = new HashMap<>(){{
^
reason: cannot use '<>' with anonymous inner classes
where K,V are type-variables:
K extends Object declared in class HashMap
V extends Object declared in class HashMap
Solution.java:55: error: cannot find symbol
stack = new ArrayList<>(capacity);
^
symbol: class ArrayList
location: class Stack<T>
where T is a type-variable:
T extends Object declared in class Stack
6 errors
Code: 10:05:46 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:38: error: wrong number of type arguments; required 2
private Map<Character> language = new HashMap<>(){{
^
Solution.java:11: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
Solution.java:13: error: cannot infer type arguments for Stack<>
Stack<Character> stack = new Stack<>();
^
reason: cannot infer type-variable(s) T
(actual and formal argument lists differ in length)
where T is a type-variable:
T extends Object declared in class Stack
Solution.java:38: error: cannot infer type arguments for HashMap<K,V>
private Map<Character> language = new HashMap<>(){{
^
reason: cannot use '<>' with anonymous inner classes
where K,V are type-variables:
K extends Object declared in class HashMap
V extends Object declared in class HashMap
4 errors
Code: 10:06:02 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>();
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:38: error: wrong number of type arguments; required 2
private Map<Character> language = new HashMap<Character>(){{
^
Solution.java:11: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
Solution.java:13: error: cannot infer type arguments for Stack<>
Stack<Character> stack = new Stack<>();
^
reason: cannot infer type-variable(s) T
(actual and formal argument lists differ in length)
where T is a type-variable:
T extends Object declared in class Stack
Solution.java:38: error: wrong number of type arguments; required 2
private Map<Character> language = new HashMap<Character>(){{
^
4 errors
Code: 10:06:41 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character> language = new HashMap<Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:38: error: wrong number of type arguments; required 2
private Map<Character> language = new HashMap<Character>(){{
^
Solution.java:11: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
Solution.java:38: error: wrong number of type arguments; required 2
private Map<Character> language = new HashMap<Character>(){{
^
3 errors
Code: 10:07:04 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.valueSet().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:11: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
Solution.java:38: error: cannot infer type arguments for HashMap<K,V>
private Map<Character, Character> language = new HashMap<>(){{
^
reason: cannot use '<>' with anonymous inner classes
where K,V are type-variables:
K extends Object declared in class HashMap
V extends Object declared in class HashMap
Solution.java:45: error: cannot find symbol
return language.valueSet().contains(c);
^
symbol: method valueSet()
location: variable language of type Map<Character,Character>
3 errors
Code: 10:07:23 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:11: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
Solution.java:38: error: cannot infer type arguments for HashMap<K,V>
private Map<Character, Character> language = new HashMap<>(){{
^
reason: cannot use '<>' with anonymous inner classes
where K,V are type-variables:
K extends Object declared in class HashMap
V extends Object declared in class HashMap
2 errors
Code: 10:07:38 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty() == 0 ) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Compile error
Solution.java:11: error: incomparable types: boolean and int
if (S.isEmpty() == 0 ) return BALANCED;
^
1 error
Code: 10:07:55 UTC,
java,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','[');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Code: 10:08:22 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Code: 10:08:51 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}
Analysis
Code: 10:08:59 UTC,
java,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Solution {
public static final int BALANCED = 1;
public static final int UNBALANCED = 0;
public int solution(String S) {
if (S.isEmpty()) return BALANCED;
Stack<Character> stack = new Stack<>(S.length());
NestedValidatorUtil util = new NestedValidatorUtil();
for (char c: S.toCharArray()) {
if (stack.isEmpty()){
if (util.isOpener(c)) {
stack.push(c);
} else {
return UNBALANCED;
}
} else {
if(util.isOpener(c)) {
stack.push(c);
} else if(util.getOpenerForGivenCloser(c) == stack.peek()){
stack.pop();
} else {
return UNBALANCED;
}
}
}
return stack.isEmpty() ? BALANCED : UNBALANCED;
}
public static class NestedValidatorUtil {
private Map<Character, Character> language = new HashMap<Character, Character>(){{
put(')','(');
put(']','[');
put('}','{');
}};
public boolean isOpener(Character c) {
return language.values().contains(c);
}
public Character getOpenerForGivenCloser(Character closer) {
return language.get(closer);
}
}
public static class Stack<T> {
public List<T> stack;
public Stack(int capacity) {
stack = new ArrayList<>(capacity);
}
public void push(T item) {
stack.add(item);
}
public T pop() {
T item = peek();
stack.remove(stack.size() - 1);
return item;
}
public T peek() {
int position = stack.size();
T item = stack.get(position - 1);
return item;
}
public boolean isEmpty() {
return stack.isEmpty();
}
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
1.381 s
OK
2.
1.425 s
OK
3.
1.402 s
OK
4.
1.391 s
OK
5.
1.400 s
OK
1.
1.370 s
OK
1.
1.414 s
OK
2.
1.393 s
OK
3.
1.421 s
OK
4.
1.426 s
OK
5.
1.465 s
OK
expand all
Performance tests
1.
2.048 s
OK
2.
1.470 s
OK
3.
1.506 s
OK
1.
1.512 s
OK
2.
1.476 s
OK
3.
1.462 s
OK
1.
2.012 s
OK
multiple_full_binary_trees
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+
✔
OK
1.
1.648 s
OK
2.
1.644 s
OK
3.
1.637 s
OK
4.
1.659 s
OK
5.
1.533 s
OK
broad_tree_with_deep_paths
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
string of the form [TTT...T] of 300 T's, each T being '{{{...}}}' nested 200-fold, length=120K+
✔
OK
1.
1.867 s
OK
2.
1.822 s
OK