A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**Ra8****Member**

Today they gave us in the LCPC training this exercise:

We define a stable string:

1- the string is {}

2- if S is a stable string then {S} is also stable

3- if S and T are stable strings then TS is also stable

examples of stable strings:

{}, {}{}, {{}{}}...

examples of unstable strings:

}{, }{{{...

Given a string of size N 2<=N<=2000 (N is given even)

find the least operations to do on a string to make it stable:

the only operation allowed is to change { to } or vice-versa

Examples:

{{ result: 1

}{ result: 2

{{{} result:1

I will post my solution soon

**arithma****Member**

```
def replacements(s):
t = s.replace("{}","")
while(t != s):
s = t
t = s.replace("{}","")
return len(t)/2
```

Ah bummer. Found something wrong with it.

[edit]Hoping the fuck-ups have ceased.

```
def replacements(s):
t = s.replace("{}","")
while(t != s):
s = t
t = s.replace("{}","")
count = 0
s = t.lstrip("}")
count += (len(t)-len(s))/2 + (len(t)-len(s))%2
t = s.rstrip("{")
count += (len(s)-len(t))/2 + (len(s)-len(t))%2
return count + len([x for x in t if x == "{"]) - len(t)/2
print replacements("}{}}}{{{")
```

*Last edited by arithma (September 6 2012)*

**Ra8****Member**

mine is similar to arithma's code

```
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s="}{{}";
int total=0;
int b=s.length()-1;
for(int i=0;i<b;i++)
{
if(s[0]=='}')
{
s[0]='{';
total++;
}
if(s[s.length()-1]=='{')
{
s[s.length()-1]='}';
total++;
}
if(s.substr(i,2)=="{}")
{
s=s.substr(0,i)+s.substr(i+2);
if(i==0)
i=-1;
else
i-=2;
}
b=s.length()-1;
}
int size=s.length();
cout << (total+size/2);
return 0;
}
```

Pages: **1**