Given a string, find minimum number of deletions required so that there will be no two consecutive repeating characters in the string.
Examples:
Input : AAABBB Output : 4 Explanation : New string should be AB Input : ABABABAB Output : 0 Explanation : There are no consecutive repeating characters.
If there are n consecutive same characters delete n-1 out of those n characters.
Algorithm:
- Define a function countDeletions that takes a string str as input and returns an integer.
- Initialize a variable ans to 0.
- Iterate over the string str from the first character till the second last character:
a. If the current character and the next character are the same, increment ans by 1. - Return ans as the minimum number of deletions required.
Pseudocode:
function countDeletions(str):
ans = 0
for i from 0 to length(str)-2:
if str[i] == str[i+1]:
ans++
return ans
Implementation:
C++
// CPP code to count minimum deletions required// so that there are no consecutive characters left#include <bits/stdc++.h>using namespace std;int countDeletions(string str){ int ans = 0; for (int i = 0; i < str.length() - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans;}// Driver codeint main(){ string str = "AAABBB"; // Function call to print answer cout << countDeletions(str); return 0;} |
Java
// Java code to count minimum deletions required// so that there are no consecutive characters leftimport java.util.*;class GFG{ static int countDeletions(String s) { int ans = 0; char[] str = s.toCharArray(); for (int i = 0; i < str.length - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans; } // Driver code public static void main(String[] args) { String str = "AAABBB"; // Function call to print answer System.out.println(countDeletions(str)); }}/* This code is contributed by Mr. Somesh Awasthi */ |
Python3
# Python code to count minimum deletions required# so that there are no consecutive characters left\def countDeletions(string): ans = 0 for i in range(len(string) - 1): # If two consecutive characters are # the same, delete one of them. if (string[i] == string[i + 1]): ans += 1 return ans # Driver codestring = "AAABBB"# Function call to print answerprint(countDeletions(string))# This code is contributed by Sachin Bisht |
C#
// C# Program to count minimum deletions// required so that there are no// consecutive characters leftusing System;class GFG{ // Function for counting deletions static int countDeletions(String s){ int ans = 0; char []str = s.ToCharArray(); for (int i = 0; i < str.Length - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans;} // Driver code public static void Main() { String str = "AAABBB"; // Function call to print answer Console.Write(countDeletions(str)); }}// This code is contributed by Nitin Mittal. |
PHP
<?php// PHP code to count minimum // deletions required so that// there are no consecutive // characters leftfunction countDeletions($str){ $ans = 0; for ($i = 0; $i < strlen($str) - 1; $i++) // If two consecutive characters are // the same, delete one of them. if ($str[$i] == $str[$i + 1]) $ans++; return $ans;} // Driver Code $str = "AAABBB"; // Function call to // print answer echo countDeletions($str); // This code is contributed by nitin mittal?> |
Javascript
<script>// javascript code to count minimum deletions required// so that there are no consecutive characters left function countDeletions(s) { var ans = 0; var str = s; for (var i = 0; i < str.length - 1; i++) // If two consecutive characters are // the same, delete one of them. if (str[i] == str[i + 1]) ans++; return ans; } // Driver code var str = "AAABBB"; // Function call to print answer document.write(countDeletions(str)); // This code is contributed by gauravrajput1 </script> |
Output
4
This article is contributed by Rohit Thapliyal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks
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!
