title: Counting Valleys
body: <p>I'm solving a question of Hackkerank, and I'm kinda stuck at this question. Since form end I have tried enough and somehow found the algorithm, but unfortunately it is not working out for most of the inputs. It is working for some test cases. Link is : <a href="https://www.hackerrank.com/challenges/counting-valleys/problem" rel="noreferrer">Counting Valleys</a></p>
  
  <p><strong>Problem Statement</strong></p>
  
  <p>Here we have to count the number of valleys does XYZ person visits. </p>
  
  <ul>
  <li>A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level.</li>
  </ul>
  
  <p>For One step up it <strong>U</strong>, and one step down it is <strong>D</strong>. We will be given the number of steps does XYZ person travelled plus the ups and down in the form of string, i.e, <strong>UUDDUDUDDUU</strong> like that.</p>
  
  <p><strong>Sample Input</strong></p>
  
  <pre><code>8
  UDDDUDUU
  </code></pre>
  
  <p><strong>Sample Output</strong></p>
  
  <pre><code>1
  </code></pre>
  
  <p><strong>Explanation</strong></p>
  
  <p>If we represent <code>_</code> as sea level, a step up as <code>/</code>, and a step down as <code>\</code>, Gary's hike can be drawn as:</p>
  
  <pre><code>_/\      _
     \    /
      \/\/
  </code></pre>
  
  <p>He enters and leaves one valley.</p>
  
  <p><strong>Algorithm</strong></p>
  
  <p>According to my theory : </p>
  
  <p>The valley starts from going down : </p>
  
  <ul>
  <li>Traverse and check the two pairs from the string</li>
  <li>Check whether the obtained string is equals <strong>DD</strong></li>
  <li>Again start a loop from the pos starting from <strong>DD</strong>, and find where the <strong>UU</strong> is falling or not</li>
  <li>Increase the count, break;</li>
  <li>Return count</li>
  </ul>
  
  <p>But this algo fail for most of the test cases </p>
  
  <p><strong>Code</strong></p>
  
  <pre><code>static int countingValleys(int n, String s) {
      int valleyVisits = 0, i=0;
      String str = "", strOne = "";
  
      /*Here we make pairs of two, in order to get the valley's visits. Since this visit starts from DD and ends at UU. So first we get the two strings and match with DD */
      while(i&lt;n){
        //Gives the two strings from i to i+2
        str = s.substring(i, i+2);
        i = i+2; //not to start from next, but to the even pair
  
        //Checking if the pair starts from DD
        if(str.equals("DD")){
          int j = i;
          /* Rerunning the loop to get the end of the valley trip that is UU from this point */
          while(j &lt; n){
            // Getting new strings starting after DD
            strOne = s.substring(j, j+2);
            j = j+2;
  
            //Similar operation, but the getting the end from DD and then breaks
            if(strOne.equals("UU")){
              valleyVisits++;
              break;
            }
          }
        }
      }
  
      return valleyVisits;
  }
  </code></pre>
  
  <p><strong>Passed Test Cases 1</strong></p>
  
  <pre><code>8
  UDDDUDUU
  
  Expected Output : 1
  </code></pre>
  
  <p><strong>Passed Test Case 2</strong></p>
  
  <pre><code>12
  DDUUDDUDUUUD
  
  Expected Output : 2
  </code></pre>
  
  <p><strong>Failed Test Case 1</strong></p>
  
  <pre><code>10
  DUDDDUUDUU
  
  Expected Output : 2
  </code></pre>
  
  <p><strong>Failed Test Case 2</strong></p>
  
  <pre><code>100
  DUDUUUUUUUUDUDDUUDUUDDDUUDDDDDUUDUUUUDDDUUUUUUUDDUDUDUUUDDDDUUDDDUDDDDUUDDUDDUUUDUUUDUUDUDUDDDDDDDDD
  
  Expected Output : 2
  </code></pre>
  
  <p>I'm there almost, but I don't know why my logic fails in here. Thanks in advance for any help. :)</p>