Given a string S of length N, the task is to count the number of substrings made up of a single distinct character.
Note: For the repetitive occurrences of the same substring, count all repetitions.
Examples:
Input: str = “neveropen”
Output: 15
Explanation: All substrings made up of a single distinct character are {“g”, “e”, “ee”, “e”, “k”, “s”, “f”, “o”, “r”, “g”, “e”, “ee”, “e”, “k”, “s”}.Input: str = “abaanndscx”
Output: 12
Naive Approach: The simplest approach to solve this problem is to generate all substrings from the given string count the number of substrings that consist of a single distinct character only.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Effective Approach: Follow the steps below to optimize the above approach:
- Initialize a variable, say ans, to store the count of such substrings.
- Iterate over the characters of the string and check if the previous character, say pre, is the same as the current character or not.
- While the previous and current characters are found to be the same, increment subs and add to the answer.
- If the previous and current characters are found to be different, then reinitialize subs to 1.
Below is the implementation of the above approach:
C++
#include <iostream>using namespace std; // Function to count the number // of substrings made up of a // single distinct character void countSubstrings(string s) { // Stores the required count int ans = 0; // Stores the count of substrings // possible by using current character int subs = 1; // Stores the previous character char pre = '0'; // Traverse the string for (auto& i : s) { // If current character is same // as the previous character if(pre == i) { // Increase count of substrings // possible with current character subs += 1; } else { // Reset count of substrings // possible with current character subs = 1; } // Update count of substrings ans += subs; // Update previous character pre = i; } cout << ans <<endl; }// Driver codeint main(){ string s = "neveropen"; countSubstrings(s); return 0;}// This code is contributed by splevel62. |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to count the number // of substrings made up of a // single distinct character static void countSubstrings(String s) { // Stores the required count int ans = 0; // Stores the count of substrings // possible by using current character int subs = 1; // Stores the previous character char pre = '0'; // Traverse the string for(char i : s.toCharArray()) { // If current character is same // as the previous character if(pre == i) { // Increase count of substrings // possible with current character subs += 1; } else { // Reset count of substrings // possible with current character subs = 1; } // Update count of substrings ans += subs; // Update previous character pre = i; } System.out.println(ans); }// Driver Codepublic static void main(String[] args){ String s = "neveropen"; countSubstrings(s);}}// This code is contributed by souravghosh0416. |
Python3
# Python3 Program to# implement the above approach# Function to count the number# of substrings made up of a# single distinct characterdef countSubstrings(s): # Stores the required count ans = 0 # Stores the count of substrings # possible by using current character subs = 1 # Stores the previous character pre = '' # Traverse the string for i in s: # If current character is same # as the previous character if pre == i: # Increase count of substrings # possible with current character subs += 1 else: # Reset count of substrings # possible with current character subs = 1 # Update count of substrings ans += subs # Update previous character pre = i print(ans)# Driver Codes = 'neveropen'countSubstrings(s) |
C#
// C# Program to // implement the above approach using System;class GFG { // Function to count the number // of substrings made up of a // single distinct character static void countSubstrings(string s) { // Stores the required count int ans = 0; // Stores the count of substrings // possible by using current character int subs = 1; // Stores the previous character char pre = '0'; // Traverse the string foreach(char i in s) { // If current character is same // as the previous character if(pre == i) { // Increase count of substrings // possible with current character subs += 1; } else { // Reset count of substrings // possible with current character subs = 1; } // Update count of substrings ans += subs; // Update previous character pre = i; } Console.WriteLine(ans); } // Driver code static void Main() { string s = "neveropen"; countSubstrings(s); }}// This code is contributed by divyesh072019. |
Javascript
<script> // Javascript Program to implement // the above approach // Function to count the number // of substrings made up of a // single distinct character function countSubstrings(s) { // Stores the required count let ans = 0; // Stores the count of substrings // possible by using current character let subs = 1; // Stores the previous character let pre = '0'; // Traverse the string for(let i = 0; i < s.length; i++) { // If current character is same // as the previous character if(pre == s[i]) { // Increase count of substrings // possible with current character subs += 1; } else { // Reset count of substrings // possible with current character subs = 1; } // Update count of substrings ans += subs; // Update previous character pre = s[i]; } document.write(ans); } let s = "neveropen"; countSubstrings(s); </script> |
Output:
15
Time Complexity: O(N)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
