Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Substring
3.
Problem Statement
3.1.
Example 1
3.1.1.
Input
3.1.2.
Output
4.
Native Approach
4.1.
Algorithm 
4.2.
Dry Run
4.3.
C++ Implementation
4.3.1.
Output
4.4.
Java Implementation
4.4.1.
Output
5.
Complexity
5.1.
Time Complexity
5.2.
Space Complexity
6.
Efficient Approach
6.1.
Algorithm
6.2.
Dry Run 
6.3.
C++ Implementation
6.3.1.
Output
6.4.
Java Implementation
7.
Complexity
7.1.
Time Complexity 
7.2.
Space Complexity
8.
Frequently Asked Questions
8.1.
What can be another approach to solve this problem?
8.2.
What do you mean by a substring?
8.3.
What is an ASCII value?
8.4.
What is the significance of the pointers l and r in the count function?
8.5.
What does it mean for a substring to have increasing ASCII values?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count of Increasing Substrings in given String

Introduction

"Hello, Ninja, welcome back! Today, we will cover counting the number of increasing substrings in a given string. We will explore the step-by-step approach to solving this problem and explain its logic. By the end of this session, you will have a solid understanding of how to approach similar problems and be able to apply this knowledge to your programming challenges. So, let's get started!"

Introduction

Before jumping into our problem statement, let’s understand the meaning of substring.

Substring

A substring is a contiguous sequence of characters within a string.

Let's understand, with an example, a string “Year.”

Substrings would be “Y”, ”e”, “a”, “r”, “Ye”, “Yea”, “Year”, “ea”, “ear”, and “ar”.

Substrings
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

Problem Statement

We will be given a string from which we have to count the number of substrings in which every character’s ASCII value is greater or equal to the ASCII value of the previous character. 

Note:

The substrings must be at least of length 2.

Example 1

Input

string = “bcdab”

Output

4

Explanation: 

ASCII value of c>b. Therefore ‘bc’ is one substring.
ASCII value of d>c. Therefore ‘cd’ is the second substring.
The third substring will combine the above substrings, i.e., ‘bcd.’
ASCII value of a<d. Therefore ‘da’ can’t be a substring.
ASCII value of b>a. Therefore ‘ab’ is the fourth substring.

Native Approach

In this approach, we will generate all possible substrings of length 2 or greater from the given input string, and then check whether every character's ASCII value is greater or equal to the ASCII value of the previous character.

By using nested loops to generate all possible substrings of length 2 or greater from the input string. Each substring uses another loop to check whether every character's ASCII value is greater or equal to the ASCII value of the previous character by comparing adjacent characters. If all characters satisfy this condition, it increments the count of valid substrings.

Algorithm
 

1. Initialize count = 0.
 

2. Loop i from 0 to n-1, where n is the length of the input string s.
 

3. Loop j from i+2 to n, where j is the end index of the current substring:
 

        i. Set valid = true

        ii. Loop k from i to j-1:

        iii.  If s[k+1] < s[k], set valid = false and break the loop

        iv. If valid is true, increment count by 1
 

4. Return count

Dry Run

Below is the dry run of the word “ninja”:

  • The input string is "ninja".

ninja

  • The length of the string is 5, so n=5.
     
  • We initialise the counter for valid substrings to 0.
     
  • We start iterating over all possible substrings of length 2 or greater.
     
  • In all the substrings, only “in” will increase the count to 1 because i<n.
substrings
  • So the result will be 1.

C++ Implementation

#include <iostream>
#include <string>

using namespace std;

int countIncreasingSubstrings(string inputStr) {

    int n = inputStr.length();

    int count = 0;
   
    // iterate all possible substrings using three for-loops
    for (int i = 0; i < n; i++) {
        for (int j = i+2; j <= n; j++) {

            bool isValid = true;
           
            // checking if characters in the substring are in increasing or not
            for (int k = i; k < j-1; k++) {

                 // if character at k+1 is smaller than character at k
                if (inputStr[k+1] < inputStr[k]) {

                    // substring is not valid
                    isValid = false;

                    // exit inner loop
                    break;
                }
            }

            // for valid substring
            if (isValid) {

                count++;
            }
        }
    }
    return count;
}

int main() {
    string inputStr = "ninja";
    int validSubstringCount = countIncreasingSubstrings(inputStr);
   
    cout << "The count of valid substrings in \"" << inputStr << "\" is: " << validSubstringCount << endl;
    return 0;
}

Output

Output

Java Implementation

import java.util.*;

public class Solution {
   
    // so basically we're passing a parameter called "inputString" to the method that's written below
    public static int countIncreasingSubstrings(String inputStr) {
       
        int n = inputStr.length();
       
        int count = 0;
       
        //  we can iterate over all possible substrings using three for-loops.
        for (int i = 0; i < n; i++) {
            for (int j = i+2; j <= n; j++) {
               
                // Let's start by assuming that the substring is valid.
                boolean isValid = true;
               
                /*
                 Next, we need to check if the characters in the substring are in increasing order.          
                */
                for (int k = i; k < j-1; k++) {
                   
                    /*
                    To do this, we can check if the character at index k+1 is smaller than the character at index k.
                     */
                    if (inputStr.charAt(k+1) < inputStr.charAt(k)) {
                       
                        isValid = false;
                       
                        break;
                    }
                }  
                if (isValid) {
                   
                    count++;
                }
            }
        }
 		return count;
    }

    public static void main(String[] args) {
       
        String inputStr = "ninja";
       
        int validSubstringCount = countIncreasingSubstrings(inputStr);
       
        // printing here
        System.out.println("The count of valid substrings in \"" + inputStr + "\" is: " + validSubstringCount);
    }
}

Output

Output

Also check out - Substr C++, and Euclid GCD Algorithm

Complexity

Time Complexity

O(n^3), where n is the length of the input string.

Reason: Because the code uses three nested for-loops to iterate over all possible substrings of the input string. 

Space Complexity

O(1)

Reason: Because it uses only a constant amount of additional memory to store the variables n, count, isValid, and the loop indices i, j, and k. 

Efficient Approach

A simple mathematical calculation will efficiently find the increasing ASCII value substrings. We maintain two pointers, left and right that initially point to the first and second characters of the input string, respectively. We move the right pointer to the right until we find a character whose ASCII value is less than the ASCII value of the previous character. At this point, we count the number of substrings that end at the previous character and add it to the total count. We then move the left pointer to the right of the previous character and continue the process until we reach the end of the string.

Algorithm

  • To store the final answer, initialise two-pointers(l and r) and a variable result.
     
  • Iterate through the String using a while loop by checking two conditions:
     
    • r is less than the length of the String and,
       
    • str[r]>=str[r-1].
       
  • Find the increasing ASCII substrings by adding initializing len = r-l, then adding (len * (len + 1) / 2) – len to result.
     
  • Increment l and r pointers.
     
  • Store the final answer in the result variable.

Dry Run 

  • Initialize the string "ninja".
ninja
  • Call the count function with the string "ninja" as an argument.
     
  • In the count function, initialize pointers l and r to 0 and 1, respectively.
initialize pointers l and r to 0 and 1
  • Iterate through the string while r is less than the length of the string.
Iterate through the string
  • Count the number of substrings with increasing ASCII values.
     
  • Since there is one substring with increasing ASCII values ("in"), the output is 1.

C++ Implementation

#include <iostream>
#include <string>

using namespace std;

int countIncreasingSubstrings(const string& str) {
    int l = 0;
    int r = 1;
    int length = str.length();
    int result = 0;

    // Iterating through out string
    while (r < length) {
        /*
  			Iterate the while loop 
  			until the string has 
  			increasing ASCII value
		*/
        while (r < length && str[r] >= str[r - 1]) {
            ++r;
        }

        // length of longest substring
        int len = r- l;

        /*
       		number of substrings with 
        	length at least 2 and 
            add it to the answer
		*/
        result += (len * (len + 1)) / 2 - len;

        l= r;
        ++r;
    }

    return result;
}

int main() {
    string str = "ninja";

    int result = countIncreasingSubstrings(str);
    cout << "The count of valid substrings in \"" << str << "\" is: " << result << endl;

    return 0;
}

Output

Output

Java Implementation

import java.util.*;

public class Solution {

    public static int count(String str) {

        int l = 0, r = 1;

        int length = str.length();

        // Initializing a variable for storing the answer
        int result = 0;

        // Iterate through the string
        while (r < length) {
            /*
  				Iterate the while loop 
  				until the string has 
  				increasing ASCII value
			*/
            while (r < length && str.charAt(r) >= str.charAt(r - 1)) {
                r++;
            }

            // Here below is the length of the longest substring.
            int len = r- l;

            /*
              number of substrings with 
              length at least 2 and 
              add it to the answer
			*/
            result += (len * (len + 1)) / 2 - len;

            l= r;
            r++;
        }

        return result;
    }

    public static void main(String[] args) {

        String str = "ninja";
		System.out.println("The count of valid substrings in \"" + str + "\" is: " + count(str));
    }
}

Output

Output

Complexity

Time Complexity 

O(n): The time complexity to solve the problem efficiently is O(n).

Reason: We are iterating through the input string once and performing constant time operations (comparisons and arithmetic operations) on each character. The while loop inside the main loop runs at most n-1 times, so its time complexity is also O(n). 

Space Complexity

O(1)

Reason: The only additional space used by the algorithm is for the variables used to keep track of the left and right pointers, the length of the input string, and the result. These variables use a constant amount of space, regardless of the input string size.

Frequently Asked Questions

What can be another approach to solve this problem?

Another naive approach is iterating through the String and counting the increasing ASCII values substrings at every index that takes O(n^2) time complexity.

What do you mean by a substring?

A substring is a sequence of characters within the string that should be contiguous.

What is an ASCII value?

An ASCII value is a numerical representation of a character in the ASCII encoding system. ASCII stands for American Standard Code for Information Interchange, and it is a widely used character encoding standard that assigns unique numerical values to each character in the English language and some special characters.

What is the significance of the pointers l and r in the count function?

The pointers l and r in the count function are used to keep track of the left and right endpoints of the current substring being processed. The l pointer is initialized to 0, and the r pointer is initialized to 1.

What does it mean for a substring to have increasing ASCII values?

A substring has increasing ASCII values if the ASCII value of each character in the substring is greater than or equal to the ASCII value of the previous character. In other words, the characters in the substring are arranged in alphabetical or numerical order.

Conclusion

This article covers the problem of finding the number of increasing substrings in a string.

We have solved this problem efficiently using simple calculations in the Java language.

The String is a basic needed part of the data structure that every programmer should cover for raising the bar of coding skills.

Recommended Problems:

You can also use Coding Ninjas Studio for various DSA questions typically asked in interviews for more practice. 

Previous article
Manacher’s Algorithm
Next article
Print all subsequences of a string
Live masterclass