"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!"
Before jumping into our problem statement, let’s understand the meaning of substring.
Substring
Asubstring 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”.
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".
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.
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
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);
}
}
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".
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.
Iterate through the string while r is less than the length of 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
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
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.
46+ registered 