# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 September 6 2012

Ra8
Member

### [Exercise] Braces

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

## #2 September 6 2012

arithma
Member

### Re: [Exercise] Braces

``````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.

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)

## #3 September 6 2012

Ra8
Member

### Re: [Exercise] Braces

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;
}``````