Nesting

Determine whether a given string of parentheses (single type) is properly nested
ℹ️ © Codility, 2009-2018

Problem

A string S consisting of n characters is called “properly nested” if:
• S is empty;
• S has the form “(U)” where U is a properly nested string;
• S has the form “VW” where V and W are properly nested strings.

For example, string “(()(())())” is properly nested but string “())” isn’t.

Write a function that, given a string S consisting of n characters, returns 1 if string 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.

Assume that:
• n is an integer within the range [0 … 1,000,000];
• string S consists only of the characters ‘(’ and/or ‘)’.

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

Solution

C#

class Solution {
  public int solution(string S) {
    int n = S.Length;
    if (n % 2 == 1) {
      return 0;
    }
    int t = 0;
    foreach (char s in S) {
      t += s == '(' ? 1 : -1;
      if (t < 0) {
        return 0;
      }
    }
    return t == 0 ? 1 : 0;
  }
}

Java

class Solution {
  public int solution(String S) {
    int n = S.length();
    if (n % 2 == 1) {
      return 0;
    }
    int t = 0;
    for (int i = 0; i < n; i++) {
      char s = S.charAt(i);
      t += s == '(' ? 1 : -1;
      if (t < 0) {
        return 0;
      }
    }
    return t == 0 ? 1 : 0;
  }
}

JavaScript

function solution(S) {
  let n = S.length;
  if (n % 2 == 1) {
    return 0;
  }
  let t = 0;
  for (let i in S) {
    let s = S[i];
    t += s == '(' ? 1 : -1;
    if (t < 0) {
      return 0;
    }
  }
  return t == 0 ? 1 : 0;
}

PHP

function solution($S) {
  $n = strlen($S);
  if ($n % 2 == 1) {
    return 0;
  }
  $t = 0;
  for ($i = 0; $i < $n; $i++) {
    $s = $S[$i];
    $t += $s == '(' ? 1 : -1;
    if ($t < 0) {
      return 0;
    }
  }
  return $t == 0 ? 1 : 0;
}