Number of ways to remove a sub-string from S such that all remaining characters are same

0 0 6 minutes read

Given a string str consisting only of lowercase English alphabets, the task is to count the number of ways to remove exactly one sub-string from str such that all remaining characters are same.

Note: There are at least two different characters in str and we can remove the whole string as well.

Examples:

Input: str = “abaa”
Output: 6
We can remove the following sub-strings to satisfy the given condition:
str[0:1], str[0:2], str[0:3], str[1:1], str[1:2] and str[1:3]

Input: str = “zambiatek”
Output: 3
We remove complete string.
We remove all except first.
We remove all except last

Approach:

Store the length of prefix and suffix of same characters from the string in variables count_left and count_right.
It is obvious that this prefix and suffix wouldn’t overlap, since there are at least two different characters in str.
Now there are 2 cases:
- When str[0] = str[n – 1] then every character of the prefix (including the character just after the prefix ends) will act as the starting character of the sub-string and every character of the suffix (including the character just before the suffix starts) will act as the ending character of the sub-string. So, total valid sub-strings will be count = (count_left + 1) * (count_right + 1).
- When str[0] != str[n – 1]. then count = count_left + count_right + 1.

Below is the implementation of the above approach:

C++

// C++ program to count number of ways of
// removing a substring from a string such 
// that all remaining characters are equal
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of ways 
// of removing a sub-string from s such
// that all the remaining characters are same
int no_of_ways(string s)
{
    int n = s.length();
 
    // To store the count of prefix and suffix
    int count_left = 0, count_right = 0;
 
    // Loop to count prefix
    for (int i = 0; i < n; ++i) {
        if (s[i] == s[0]) {
            ++count_left;
        }
        else
            break;
    }
 
    // Loop to count suffix
    for (int i = n - 1; i >= 0; --i) {
        if (s[i] == s[n - 1]) {
            ++count_right;
        }
        else
            break;
    }
 
    // First and last characters of the
    // string are same
    if (s[0] == s[n - 1])
        return ((count_left + 1) * (count_right + 1));
 
    // Otherwise
    else
        return (count_left + count_right + 1);
}
 
// Driver function
int main()
{
    string s = "zambiatek";
    cout << no_of_ways(s);
 
    return 0;
}

Java

// Java program to count number of ways of
// removing a substring from a string such 
// that all remaining characters are equal
import java.util.*;
 
class solution
{
 
// Function to return the number of ways 
// of removing a sub-string from s such
// that all the remaining characters are same
static int no_of_ways(String s)
{
    int n = s.length();
 
    // To store the count of prefix and suffix
    int count_left = 0, count_right = 0;
 
    // Loop to count prefix
    for (int i = 0; i < n; ++i) {
        if (s.charAt(i) == s.charAt(0)) {
            ++count_left;
        }
        else
            break;
    }
 
    // Loop to count suffix
    for (int i = n - 1; i >= 0; --i) {
        if (s.charAt(i) == s.charAt(n - 1)) {
            ++count_right;
        }
        else
            break;
    }
 
    // First and last characters of the
    // string are same
    if (s.charAt(0) == s.charAt(n - 1))
        return ((count_left + 1) * (count_right + 1));
 
    // Otherwise
    else
        return (count_left + count_right + 1);
}
 
// Driver function
public static void main(String args[])
{
    String s = "zambiatek";
    System.out.println(no_of_ways(s));
 
}
}

Python3

# Python 3 program to count number of 
# ways of removing a substring from a 
# string such that all remaining
# characters are equal
 
# Function to return the number of 
# ways of removing a sub-string from 
# s such that all the remaining 
# characters are same
def no_of_ways(s):
    n = len(s)
 
    # To store the count of 
    # prefix and suffix
    count_left = 0
    count_right = 0
 
    # Loop to count prefix
    for i in range(0, n, 1):
        if (s[i] == s[0]):
            count_left += 1
        else:
            break
 
    # Loop to count suffix
    i = n - 1
    while(i >= 0):
        if (s[i] == s[n - 1]):
            count_right += 1
        else:
            break
 
        i -= 1
 
    # First and last characters of 
    # the string are same
    if (s[0] == s[n - 1]):
        return ((count_left + 1) *
                (count_right + 1))
 
    # Otherwise
    else:
        return (count_left + count_right + 1)
 
# Driver Code
if __name__ == '__main__':
    s = "zambiatek"
    print(no_of_ways(s))
 
# This code is contributed by
# Sahil_shelengia

C#

// C# program to count number of ways of
// removing a substring from a string such 
// that all remaining characters are equal
using System;
 
class GFG
{
 
// Function to return the number of ways 
// of removing a sub-string from s such
// that all the remaining characters are same
static int no_of_ways(string s)
{
    int n = s.Length;
 
    // To store the count of prefix and suffix
    int count_left = 0, count_right = 0;
 
    // Loop to count prefix
    for (int i = 0; i < n; ++i) 
    {
        if (s[i] == s[0]) 
        {
            ++count_left;
        }
        else
            break;
    }
 
    // Loop to count suffix
    for (int i = n - 1; i >= 0; --i) 
    {
        if (s[i] == s[n - 1]) 
        {
            ++count_right;
        }
        else
            break;
    }
 
    // First and last characters of the
    // string are same
    if (s[0] == s[n - 1])
        return ((count_left + 1) * 
                (count_right + 1));
 
    // Otherwise
    else
        return (count_left + count_right + 1);
}
 
// Driver Code
public static void Main()
{
    string s = "zambiatek";
    Console.WriteLine(no_of_ways(s));
}
}
 
// This code is contributed 
// by Akanksha Rai

PHP

<?php
// PHP program to count number of ways of
// removing a substring from a string such 
// that all remaining characters are equal
 
// Function to return the number of ways 
// of removing a sub-string from $s such
// that all the remaining characters are same
function no_of_ways($s)
{
    $n = strlen($s);
 
    // To store the count of prefix and suffix
    $count_left = 0;
    $count_right = 0;
 
    // Loop to count prefix
    for ($i = 0; $i < $n; ++$i) 
    {
        if ($s[$i] == $s[0]) 
        {
            ++$count_left;
        }
        else
            break;
    }
 
    // Loop to count suffix
    for ($i = $n - 1; $i >= 0; --$i) 
    {
        if ($s[$i] == $s[$n - 1]) 
        {
            ++$count_right;
        }
        else
            break;
    }
 
    // First and last characters of the
    // string are same
    if ($s[0] == $s[$n - 1])
        return (($count_left + 1) * 
                ($count_right + 1));
 
    // Otherwise
    else
        return ($count_left + $count_right + 1);
}
 
// Driver Code
$s = "zambiatek";
echo no_of_ways($s);
 
// This code is contributed by ihritik
?>

Javascript

<script>
 
    // JavaScript program to count number of ways of
    // removing a substring from a string such 
    // that all remaining characters are equal
     
    // Function to return the number of ways 
    // of removing a sub-string from s such
    // that all the remaining characters are same
    function no_of_ways(s)
    {
        let n = s.length;
 
        // To store the count of prefix and suffix
        let count_left = 0, count_right = 0;
 
        // Loop to count prefix
        for (let i = 0; i < n; ++i) 
        {
            if (s[i] == s[0]) 
            {
                ++count_left;
            }
            else
                break;
        }
 
        // Loop to count suffix
        for (let i = n - 1; i >= 0; --i) 
        {
            if (s[i] == s[n - 1]) 
            {
                ++count_right;
            }
            else
                break;
        }
 
        // First and last characters of the
        // string are same
        if (s[0] == s[n - 1])
            return ((count_left + 1) * 
                    (count_right + 1));
 
        // Otherwise
        else
            return (count_left + count_right + 1);
    }
     
    let s = "zambiatek";
    document.write(no_of_ways(s));
 
</script>

Output

Complexity Analysis:

Time Complexity: O(n), where n is the size of the given string
Auxiliary Space: O(1), as no extra space is required

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 zambiatek!