title: Why does this solution fail? Nested and matching brackets
body: <p>I am still failing tests for </p>
  
  <ul>
  <li><code>"negative_match: invalid structures,"</code>;</li>
  <li><code>"simple_grouped: simple grouped positive and negative test, length=22"</code>;</li>
  <li><code>"large1 simple large positive test, 100K ('s followed by 100K )'s + )("</code>; and </li>
  <li><code>"large2 simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()"</code>. </li>
  </ul>
  
  <p>Can anyone see what my error is? The code I wrote works for all strings I tested...</p>
  
  <p>Here is a description of the task:</p>
  
  <blockquote>
    <p>A string <code>S</code> consisting of <code>N</code> characters is considered to be properly
    nested if any of the following conditions is true:</p>
    
    <ul>
    <li><code>S</code> is empty; </li>
    <li><code>S</code> has the form <code>"(U)"</code> or <code>"[U]"</code> or <code>"{U}"</code> where <code>U</code> is a properly nested string; </li>
    <li><code>S</code> has the form <code>"VW"</code> where <code>V</code> and <code>W</code> are properly nested strings.</li>
    </ul>
    
    <p>For example, the string <code>"{[()()]}"</code> is properly nested but <code>"([)()]"</code> is
    not.</p>
    
    <p>Write a function: </p>
    
    <p><code>def solution(S)</code> </p>
    
    <p>that, given a string <code>S</code>
    consisting of <code>N</code> characters, returns <code>1</code> if <code>S</code> is properly nested and <code>0</code>
    otherwise. For example, given <code>S = "{[()()]}"</code>, the function should
    return <code>1</code> and given <code>S = "([)()]"</code>, the function should return <code>0</code>, as
    explained above. </p>
    
    <p>Assume that:</p>
    
    <ul>
    <li><code>N</code> is an integer within the range <code>[0..200,000]</code>;</li>
    <li>string <code>S</code> consists only of the following characters: <code>"("</code>, <code>"{"</code>, <code>"["</code>, <code>"]"</code>, <code>"}"</code> and/or <code>")"</code>.</li>
    </ul>
    
    <p><strong>Complexity</strong>: expected worst-case time complexity is <code>O(N)</code>; expected
    worst-case space complexity is <code>O(N)</code> (not counting the storage required
    for input arguments).</p>
  </blockquote>
  
  <p>Here is my solution:</p>
  
  <pre><code>def solution(S):
  # write your code in Python 2.7
  if S == "":
      return 1
  length = len(S)
  start = 0
  end = length-1
  
  if length%2 != 0:
      return 0
  
  for i in range(0, length):
      if (S[start] == '(') and (S[end] != ')'):
          return 0
      if (S[start] == '[') and (S[end] != ']'):
          return 0
      if (S[start] == '{') and (S[end] != '}'):
          return 0
      start = start +1
      end = end -1
  
  return 1    
  
  pass
  </code></pre>