Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Code in C++
3.4.
Code in Python
3.5.
Complexity
4.
Frequently Asked Questions
4.1.
How can you compare two strings in c++?
4.2.
How can you find the length of a string in C++?
4.3.
How to convert a string into an integer using the C++ STL function?
4.4.
How to convert a string in uppercase or lowercase in C++?
4.5.
What is the difference between a character and a string?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Count Valleys

Author Rishabh
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This article will look at a problem involving strings. A variety of string problems are asked in top tech companies. The problem we will be discussing today is also a string problem. 

Introduction Image

This problem will test your observation skills. So why to wait? Let’s jump to the question.

Problem Statement

You are given an integer ‘N’ (number of steps) and a string racetrack’, which is a permutation of ‘U’ (ups) and ‘D’ (downs). Races always start and end at ground level, and each step up or down represents a 1-unit change in altitude.

For example, Given, racetrack = “UDDUUDDDUU”.

We can observe that a valley can be represented as:

  • Valley: Sequence of downhill and uphill starting and ending at ground level. For example: ‘DDUU’.
problem statement image

You have to calculate the number of valleys in the racetrack.

Example

Input

racetrack = “UDDUUDDDUU”

Output 

2

Explanation

We can see from the input that there are 2 combinations of ‘DDUU’ in the string “racetrack”. Hence, the output is 2.

example image
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

We will traverse the string ‘racetrack’ and check 

  1. If it is an up step, increase the level by 1.
    1. Check if 'LEVEL' == 0.
    2. If 'LEVEL' == 0, increase the 'NO_OF_VALLEYS' count by 1.
       
  2. If it is a down step, reduce the level by 1.

Algorithm

  1. Initialize LEVEL = 0, starting at ground level.
     
  2. Initialize the count of valleys, i.e., noOfValleys to zero.
     
  3. For each step in the racetrack from ‘i = 0’ to ‘i < n’:
    a. If the current step is an up step (represented by 'U'), increase LEVEL by 1.
    b. If the current step is a down step (represented by 'D'), decrease LEVEL by 1.
    c. If the LEVEL becomes zero after taking a step, increment the count of valleys by 1.
     
  4. Return the count of valleys.

Dry Run

  1. Initialize the level variable to 0 and noOfValleys to 0.
     
  2. Loop through the racetrack string “UDDUUDDDUU”
    1. When the current step is 'U':
    2. Increase the level by 1.
    3. If level is now 0, then we have crossed a valley, so increase noOfValleys by 1.
       
  3. When the current step is 'D':
    1. Decrease the level by 1.
       
  4. After the loop ends, return the noOfValleys.
dry run

5. Finally, return the noOfValleys as 2.

Code in C++

#include <iostream>
#include <string>
using namespace std;

// Function to count valleys we have crossed in the racetrack.
int countValleys(int n, string racetrack){
    // Initialize LEVEL = 0, starting at ground level.
    int level = 0;
    // Initialize count of valleys to zero.
    int noOfValleys = 0;

    for (int i = 0; i < n; i++){
        /*
            If the current step is an 
            up step increase the LEVEL by 1.
        */
        if (racetrack[i] == 'U'){
            level++;
            /*
                Check if after an up step our LEVEL = 0, 
                then we know we have crossed a valley so 
                increase the count of valleys by 1.
            */
            if (level == 0){
                noOfValleys++;
            }
        }
        /*
            If the current step is a down step,
            then decrease the LEVEL by 1.
        */
        else{
            level--;
        }
    }
    // return the count of valleys.
    return noOfValleys;
}
int main(){
    int n=11;
    string racetrack="UDDUUDDDUU";
    
    // Calling count valleys function. 
    int noOfValleys = countValleys(n, racetrack);
    cout << noOfValleys << endl;
    return 0;
}


Output
 

output 1

Code in Python

# Function to count valleys we have crossed in the racetrack.
def count_valleys(n, racetrack):
    # Initialize LEVEL = 0, starting at ground level.
    level = 0
    
    # Initialize count of valleys to zero.
    no_of_valleys = 0
    
    for i in range(min(n, len(racetrack))):
        # If the current step is an up step,
        # increase the LEVEL by 1.
        if racetrack[i] == 'U':
            level += 1
            # Check if after an up step our LEVEL = 0, 
            # then we know we have crossed a valley so 
            # increase the count of valleys by 1.
            if level == 0:
                no_of_valleys += 1
        # If the current step is a down step, 
        # then decrease the LEVEL by 1.
        else:
            level -= 1
    
    # Return the count of valleys.
    return no_of_valleys

n = 11
racetrack = "UDDUUDDDUU"

# Calling count valleys function. 
no_of_valleys = count_valleys(n, racetrack)

print(no_of_valleys)


Output
 

output 2

Complexity

Time Complexity = O(N),
where ‘N’ is the number of steps on the ‘racetrack’.
We traverse the whole string once. So our time complexity is O(N).

Space Complexity = O(1)
Since we are not using any extra space, space complexity is O(1).

Also see, Rabin Karp Algorithm

Must Read Python String Concatenation

Frequently Asked Questions

How can you compare two strings in c++?

You can use the ‘compare()’ method to compare two strings. We can also use operators ‘==’ and ‘!=’ to compare. We can also use the ‘strcmp()’ function when using string.

How can you find the length of a string in C++?

You can use the ‘length()’ method of the string class in C++ to find the length of a string. We can also use the ‘size()’ and ‘strlen()’ functions.

How to convert a string into an integer using the C++ STL function?

We can use the ‘stoi’ function from C++ STL to convert a string into an integer.

How to convert a string in uppercase or lowercase in C++?

We can convert a string to uppercase or lowercase using the “toupper()” or “tolower()” function in C++.

What is the difference between a character and a string?

A character is a single symbol or letter, while a string is a sequence of characters.

Conclusion

In this blog, we learned about the count valleys problem. We have implemented the problem in C++ and python programming languages.

For more string data structure articles, you can refer following links:

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Find the longest proper prefix that is also a suffix
Next article
Convert Given Array of Strings to a Camel Case Format Sentence
Live masterclass