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

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 = “geeksforgeeks”Output:3

We remove complete string.

We remove all except first.

We remove all except last

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**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**.

- When

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 = ` `"geeksforgeeks"` `;` ` ` `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 = ` `"geeksforgeeks"` `;` ` ` `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 ` `=` `"geeksforgeeks"` ` ` `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 = ` `"geeksforgeeks"` `;` ` ` `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` `= ` `"geeksforgeeks"` `;` `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 = ` `"geeksforgeeks"` `;` ` ` `document.write(no_of_ways(s));` `</script>` |

**Output:**

3