in ,

Minimum number of insertions in given String to remove adjacent duplicates

Given a string str of size N, the task is to find the minimum number of additions in the string such that no two consecutive elements are the same.


Input: str=”rrg” 
Output: 1
Explanation: Add an element between two r’s

Input: str=”rrrrr”
Output: 4


Approach: The above problem can be solved using the above steps:

  1. Declare variable min_steps and initialise it by 0.
  2. Traverse the string using a for-loop from i=0 to i.
  3. Check if the current character is the same as the character before it.
  4. If yes, then increment min_steps by 1.
  5. Else, continue the loop.
  6. Print min_steps as the answer.

Below is the implementation of the above approach:




using namespace std;


int minAdditions(string str)



    int len = str.size();




    int min_steps = 0;


    int i;




    for (i = 1; i < len; i++) {

        if (str[i] == str[i - 1])





    return min_steps;



int main()


    string str = "RRG";

    cout << minAdditions(str);

    return 0;




def minAdditions(str):



    le = len(str)




    min_steps = 0




    for i in range(1, le):

        if (str[i] == str[i - 1]):

            min_steps += 1



    return min_steps



if __name__ == "__main__":


    str = "RRG"





Time Complexity: O(N)
Auxiliary Space: O(1)


What do you think?

Silver 1

Written by yulica

Leave a Reply

Your email address will not be published.

      Minimize operations to convert (0, 0) to (N, M) by incrementing either or both by K

      SCAND Is Celebrating Its 20th Anniversary_61d8c28bb0417.jpeg

      SCAND Is Celebrating Its 20th Anniversary