-
Notifications
You must be signed in to change notification settings - Fork 368
/
Beautiful_string.cpp
68 lines (67 loc) · 1.9 KB
/
Beautiful_string.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*Name : Atul Kumar
Github username : atul1510
Repositary name : Algorithms
*/
/* Problem Statement: Atul has been given a binary string ‘STR’ containing either ‘0’ or ‘1’. A binary string is called beautiful if it contains alternating 0s and 1s.
For Example:‘0101’, ‘1010’, ‘101’, ‘010’ are beautiful strings.
He wants to make ‘STR’ beautiful by performing some operations on it. In one operation, Atul can convert ‘0’ into ‘1’ or vice versa.
Your task is to determine the minimum number of operations Atul should perform to make ‘STR’ beautiful.
Time Complexity:- O(n)
*/
#include<bits/stdc++.h>
using namespace std;
// Method to count minimum number of operations that should perform to make ‘STR’ beautiful.
int Beautiful(string str)
{
int m = str.length(); // iterating over array of all substrings
int x1 = 0, x2 = 0;
char s1 = '0', s2 = '1';
for (int i = 0; i < m; i++)
{
if (str[i] == '1') // if number of ones,two and zero are equal in a substring
{
if (s1 == '0')
{
x1++;
}
else {
x2++;
}
}
else
{
if (s1 == '1')
{
x1++;
}
else
{
x2++;
}
}
if (s1 == '1')
{
s1 = '0';
s2 = '1';
}
else
{
s1 = '1';
s2 = '0';
}
}
return min(x1, x2);
}
int main() //Main Function
{
int test; // For Test Cases
cout<<"Enter total testcases: "<<endl;
cin>>test;
while(test--)
{
string str; // Initalise a string
cin>>str;
cout<<Beautiful(str)<<endl; // Function call
}
return 0;
}