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.

Examples:

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:

C++

 

#include

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])

            min_steps++;

    }

 

    

    return min_steps;

}

 

int main()

{

    string str = "RRG";

    cout << minAdditions(str);

    return 0;

}

Python3

 

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"

    print(minAdditions(str))

 

 
 

 

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