Facebook Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
Hey it works for your case:
aaaabbbb -> aaacbbb -> aaaabb -> aaacb -> aabb -> acb -> bb
so the length is 2
It might works when 3 different letters are given, what if we input more letters like abcddcca
Use math induction:
1. if you have case of length 3
if all the same then 3
if all different then 1 (i.e. odd counts)
other cases 2
2. Lemma: If string of length N > 3 consist of non same char it always can be reduced to the length N - 1. (prove is simple)
3. Lemma: If string is N > 3 and consist of non same char during reduction to N-1 it may be represented as a string of non the same chars (reader can prove it too as it's not too hard)
4. Lemma: during reduction from N to N-1 (N > 3) if number of chars been all odd then it will become even and reverse. This is super easy to prove.
Now if you take all this lemmas you can easy to see a logic why it works. First you can always reduce a chain of non same chars up to the string with 3 chars, secondary during reduction you'll end up with odd count if you start count have been even or odd.
it wont work.
As your alg, aaabbb and aacbb should return different values.
however, they are actually the same string...
try aaabbb, it should return 1 but you algorithm return 2
aacbb->aaab->aac->ab->c so it should return 1
aaabbb should return 1 and he does return 1. please check your work over before commenting :)
#include<iostream>
#include<string>
using namespace std;
bool isequal(string s)
{
int i=0;
while(i<s.length()-1)
{
if(s[i]!=s[i+1])
{
return false;
}
i++;
}
return true;
}
char cnot(char r,char s)
{
if(r=='a'&&s=='b')
{
return 'c';
}
else if(r=='a'&&s=='c')
{
return 'b';
}
else if(r=='b'&&s=='a')
{
return 'c';
}
else if(r=='b'&&s=='c')
{
return 'a';
}
else if(r=='c'&&s=='a')
{
return 'b';
}
else if(r=='c'&&s=='b')
{
return 'a';
}
}
int length(string s)
{
int i,n;
while(!isequal(s))
{
n=s.length();
i=0;
while(i<n-1)
{
if(s[i]!=s[i+1])
{
s[i]=cnot(s[i],s[i+1]);
s=s.substr(0,i+1)+s.substr(i+2);
n=s.length();
}
else
{
i++;
}
}
}
return s.length();
}
int main()
{
int t,*a;
string *s;
cin>>t;
s=new string[t];
for(int i=0;i<t;i++)
{
cin>>s[i];
}
a=new int[t];
for(int i=0;i<t;i++)
{
a[i]=length(s[i]);
}
for(int i=0;i<t;i++)
{
cout<<a[i]<<"\n";
}
return 0;
}
hope this code will be useful...
Ishant, you are correct (though there's still something missing ...). So let me list all possible cases:
(1) String contains only one kind of characters, or more precisely, the string contains k identical characters and nothing else. Clearly, no reduction is poosible and the minimum length is k.
(2) String contains 2 or 3 kinds of characters. Then if all the counts are even or all the counts are odd, the minimum string possible has length 2, otherwise we can reduce it to 1.
Proof (of 2):
With every reduction, the count of 2 characters decreases by 1, and the count of the third character increases by 1. So if all counts are even before reduction, all counts will be odd after reduction, and if allcounts are odd before, they will all be even after. So, for such strings, the shortest possible string we can get is (0, 0, 2) or (cc) or (bb) or (aa). All even counts. This proves that we can't do any better than (0, 0, 2).
Now, are we guaranteed that we can always get to (0,0,2) for the all-odd, all-even strings and to (0,0,1) for the other strings? YES! We just have to be smart about which pairs we reduce. For example, if our string is aaaaaaabc we can either reduce ab or bc. Reducing bc would mean no more reduction so we don't want to do that! So the algorithm to reach minimum string is this -- always reduce a pair that contains a character with maximum count. It does not matter which pair, just that the max count character be reduced. This will eventually result in a string of length 1 or 2 depending on the initial counts.
could you please give a proof for the part - "So, for ***such strings***, the shortest possible string we can get is (0, 0, 2) or (cc) or (bb) or (aa). "
***such strings*** -- Strings containing 2 or 3 kinds of characters and all the counts are even or all the counts are odd
Not sure what you mean ...
The first part of the proof says that for string with all odd counts or all even counts we cannot get any better than (0,0,2). Why, because each reduction brings us from all even to all odd or from all odd to all even. The shortest possible string with all even is (0,0,0) but that cannot be achieved by any reduction, so the next all-even shortest string is (0,0,2). The shortest possible all-odd string is (1,1,1) but that is (a) longer than (0,0,2) and (b) can be reduced to (0,0,2) by one reduction. Note that (0,0,1) is neither all-odd nor all-even so all-odd/all-even strings cannot be reduced to that. Anyway, the first part of the proof is that we cannot do any better than (0,0,2).
The second part of the proof is trying to prove the fact that (using smart reduction) we can indeed make it all the way to (0,0,2) for all-even/all-odd strings, and all the way to (0,0,1) for all the other strings as long the string we are starting from contains 2 or 3 different kinds of characters.
Let me give you an example:
all-odd string (3,1,1): (aaabc)->aacc->abc->cc
regular string (4,1,1): (aabaac)->acaac->baac->cac->bc->a
Hopefully this made it clear :-)
hey, i think this is not correct. i have seen instances when all the occurances are equal and odd, then it reduces to 1 char. the 2nd last comment is right in this thread.
Give me just one such instance ... Anybody can say "I have seen ...".
I proved that it's mathematically imposible. If you think the proof is not correct, show me what exactly is wrong or give me a specific counter-example. Otherwise we are wasting time here.
Man I always regret posting to this site ...
There is a counter-example
"abababab"--> "bb"; length = 2
but
"ababababab"-->"c"; length = 1
must depend on how many 'a', 'b' and 'c' the input has; seems with equal number of 'a', 'b' and 'c' the min is 2, otherwise 1. if you just look at the numbers (4,3,5) the way to the min must be through keeping the three counts as close as possible.
4,3,5->3,4,4->4,3,3->3,2,4->2,3,3->3,2,2->2,1,3->1,2,2->2,1,1->1,0,2->0,1,1->1,0,0
3,3,3->2,2,4->1,3,3->2,2,2->1,1,3->2,0,2->1,1,1->0,0,2
waiting for counter examples, thanks
For aabbccc, its 1, but min consecutive is 2. aabbccc to aabacc to aabbc to acbc to bbc to ba to c.
Better is to look at proof rather than counter example.
what do you mean by min consecutive is 2? thnx
aabbccc
2,2,3->3,1,2->2,2,1->1,1,2->0,2,1->1,1,0->0,0,1
Well it appears to be that it is going to be either 1 or 2 but with a b c as unequal also the min value will come to 2 for e.g. try acbcc -> aacc -> abc -> cc
If i, j, k are the number of occurrences of a, b, c respectively where i, j, k >= 1
and if b,a,a,c is a possible combination then the answer is '1'.
Eg.
b,a,a,c can be converted to (b,a),(a,c) => c,b => a
If either all characters are present odd no of times or all are present even number of times, in tht case the result will be 2 and in any other case the result will be 1. Please suggest a case where this does not hold true.
@ishant , pretty much correct but if we have chars appears different counts the it will also come to count as 2 ,keep it up :)
yes u r right, if given is ab or ac or bc in tht case too it will be 1. looks like what i wrote is true for strings greater or equal to of length 3
# of consecutive characters besides matters.
E.G. aaaab, the # of a is even => absorbed to one b.
aaab, the # of a is odd => absorbed to c, a different char other than a and b.
#include <iostream>
#include <string>
using namespace std;
int absorbstr(string str)
{
if (str.empty()) return 0;
if (str.size()==1) return 1;
if (str.size()==2) return str[0]==str[1]?2:1;
int num = 0;
for (size_t ix = 0; ix!=str.size()-1; ++ix)
if(str[ix]!=str[ix+1]) num = ix;
int last_size = str.size()-1-num;
int count = 1;
for (size_t ix = 0; ix!=str.size()-1; ++ix)
{
if (str[ix]==str[ix+1]) ++count;
else {
if( ix==num ) {
if(!(count%2) && !(last_size%2))
return count<last_size?count:last_size;
else return 1;
}
if( count%2 ) str[ix+1] = str[ix]^str[ix+1]^'a'^'b'^'c';
count = 1;
}
}
return count;
}
int main(int argc, char* argv[])
{
cout << argv[1] << "=>" << absorbstr(argv[1]) << endl;
return 1;
}
//a really dumb solution using DP
public class Test {
String needTest = "cab";
int sum = 'a' + 'b' + 'c';
Test()
{
System.out.println(testString(needTest));
}
int testString(String s)
{
int min = s.length();
if(min == 1)
{
return 1;
}else if(min == 2)
{
if(s.charAt(0) == s.charAt(1))
{
return 2;
}else
{
return 1;
}
}
StringBuffer sb = new StringBuffer();
for(int i= 1; i<s.length() ; i++)
{
if(s.charAt(i) != s.charAt(i-1))
{
sb = new StringBuffer();
sb.append(s.substring(0, i-1));
sb.append((char)(sum - s.charAt(i) - s.charAt(i-1)));
if(i<s.length()-1)
{
sb.append(s.substring(i+1));
}
int temp = testString(sb.toString());
if(min > temp)
{
min = temp;
}
}
}
return min;
}
public static void main(String[] argv)
{
Test t = new Test();
}
}
public class Main {
public static char get(char a, char b) {
if (a == 'a') {
if (b == 'b') return 'c';
else return 'b';
} else if (a == 'b') {
if (b == 'a') return 'c';
else return 'a';
} else {
if (b == 'b') return 'a';
else return 'b';
}
}
public static void main(String[] args) {
String test = "abbbbbbbbc";
for (int times = 0; times < test.length(); times++) {
StringBuffer sb = new StringBuffer();
sb.append(test.charAt(0));
for (int i = 1; i < test.length(); i++) {
if (test.charAt(i) != sb.charAt(sb.length() - 1)) {
char rep = get(test.charAt(i), sb.charAt(sb.length() - 1));
sb.deleteCharAt(sb.length() - 1);
sb.append(rep);
} else {
sb.append(test.charAt(i));
}
}
test = sb.toString();
}
System.out.println(test);
}
}
take the array with O(n)
Walk through original array and whenever two adjacent character diff replace it and keep the final result in second array
apply the same with second array,
Repeat above procedure unless all elements are same or length equal to 1.
Time O(n^2)
Space O(n)
Space complexity can avoided if be put the result back to original array .
We should look for optimum solutions here. It is not enough if we just parse the elements from left to right or right to left. we must find out proper combinations to achieve maximum compression.
EG : cabb
Parsing from left to right yields -> cabb -> bbb -> String of lenght 3
Parsing from right to left yields -> cabb -> ccb -> ca-> b -> string of length 1.
Hence we must check when we combine two adjacent chars to produce the resultant char, if the resultant char is same as the next char. If so, skip this pair for that round and continue.
here is the idea:
(1) allocate an array of vector<string> size equal of length of the input array.
(2) initialize this array by pushing sub-string(inputstring, 0 , i)
(3) for each item from the array, domerge from the last char to the first char(merge reversely)and push newly generated string to the vector. try combining the tail char with all strings in its previous array element (i-1)
(4) loop (3) for all array elements
(5) the length of the shortest string in the last array element will be the answer.
here is the idea:
(1) allocate an array of vector<string> size equal of length of the input array.
(2) initialize this array by pushing sub-string(inputstring, 0 , i)
(3) for each item from the array, domerge from the last char to the first char(merge reversely)and push newly generated string to the vector. try combining the tail char with all strings in its previous array element (i-1)
(4) loop (3) for all array elements
(5) the length of the shortest string in the last array element will be the answer.
here is the idea:
(1) allocate an array of vector<string> size equal of length of the input array.
(2) initialize this array by pushing sub-string(inputstring, 0 , i)
(3) for each item from the array, domerge from the last char to the first char(merge reversely)and push newly generated string to the vector. try combining the tail char with all strings in its previous array element (i-1)
(4) loop (3) for all array elements
(5) the length of the shortest string in the last array element will be the answer.
I also have an solution but in a recursive manner :
public class StringReduction {
public char getChar(char l, char r) {
if (l == 'a') {
if (r == 'b')
return 'c';
if (r == 'c')
return 'b';
}
if (l == 'b') {
if (r == 'a')
return 'c';
if (r == 'c')
return 'a';
}
if (l == 'c') {
if (r == 'a')
return 'b';
if (r == 'b')
return 'a';
}
return 'l';
}
public int redux(String input, int pos) {
if (pos > input.length() - 1) {
return input.length();
}
char l = input.charAt(pos);
char r = input.charAt(pos + 1);
if (l != r) {
StringBuffer sb = new StringBuffer(getChar(l, r));
sb.append(input.substring(pos + 1));
System.out.println(sb.toString());
return redux(sb.toString(), pos + 1);
}
return redux(input, pos + 1);
}
/**
* @param args
*/
public static void main(String[] args) {
StringReduction sr = new StringReduction();
System.out.println(sr.redux("aacbca", 0));
}
}
#include <stdio.h>
#include <string.h>
#define A 'a'
#define B 'b'
#define C 'c'
void compress(char c[], int l) {
int i=0;
int sum=0, rem=0, avg;
for (i=0;i<l;i++) sum += c[i];
rem = sum % l;
avg = sum / l;
//check if all elements are same
if((avg==A && !rem) || (avg==B && !rem) || (avg==C && !rem)) return;
if(l==2) {
c[0]=A+B+C-c[0]-c[1];
c[1]='\0';
return;
}else{
while((i+2)<l) {
if((c[i+0]+c[i+1]+c[i+2])==(A+B+C)) {
if(c[i+3]!=c[i+2])
c[i+0]=c[i+2];
else
c[i+0]=c[i+1];
memmove(&c[i+1], &c[i+2], l-i);
c[l]='\0'; --l;
continue;
}
i++;
}
i=0;
while((i+1)<l) {
if(((c[i+0]+c[i+1])==(A+B))|| ((c[i+0]+c[i+1])==(B+C)) || ((c[i+0]+c[i+1])==(A+C))){
c[i+0]=A+B+C-c[i+0]-c[i+1];
memmove(&c[i+1], &c[i+2], l-i);
c[l]='\0'; --l;
continue;
}
i++;
if(i==l && l>2)
i=0;
}
compress(c,l);
}
}
int main(void) {
int i, len;
char c[40];
printf("Enter string {a,b,c}* : ");
scanf("%s",c);
len=strlen(c);
printf("String is : %s\n",c);
compress(c,len);
printf("String is : %s\n",c);
return 0;
}
#include <stdio.h>
#include <string.h>
#define A 'a'
#define B 'b'
#define C 'c'
void compress(char c[], int l) {
int i=0;
int sum=0, rem=0, avg;
for (i=0;i<l;i++) sum += c[i];
rem = sum % l;
avg = sum / l;
//check if all elements are same
if((avg==A && !rem) || (avg==B && !rem) || (avg==C && !rem)) return;
if(l==2) {
c[0]=A+B+C-c[0]-c[1];
c[1]='\0';
return;
}else{
while((i+2)<l) {
if((c[i+0]+c[i+1]+c[i+2])==(A+B+C)) {
if(c[i+3]!=c[i+2])
c[i+0]=c[i+2];
else
c[i+0]=c[i+1];
memmove(&c[i+1], &c[i+2], l-i);
c[l]='\0'; --l;
continue;
}
i++;
}
i=0;
while((i+1)<l) {
if(((c[i+0]+c[i+1])==(A+B))|| ((c[i+0]+c[i+1])==(B+C)) || ((c[i+0]+c[i+1])==(A+C))){
c[i+0]=A+B+C-c[i+0]-c[i+1];
memmove(&c[i+1], &c[i+2], l-i);
c[l]='\0'; --l;
continue;
}
i++;
if(i==l && l>2)
i=0;
}
compress(c,l);
}
}
int main(void) {
int i, len;
char c[40];
printf("Enter string {a,b,c}* : ");
scanf("%s",c);
len=strlen(c);
printf("String is : %s\n",c);
compress(c,len);
printf("String is : %s\n",c);
return 0;
}
Code for String manipulation:
correct me if i went wrong.........
#include<stdio.h>
#include<string.h>
void main()
{
int i;
char s[10]={'a','b','c','c','c','c','c','c','c'};
printf("\n\t");
for(i=0;i<10;i++)
{
if(s[1]=='b'&&s[2]=='c')
{
printf("aacccccc");
}
if(s[1]=='a'&&s[2]=='c')
{
printf("abccccc");
}
if(s[1]=='b'&&s[2]=='c')
{
printf("aacccc");
}
if(s[1]=='a'&&s[2]=='c')
{
printf("abccc");
}
if(s[1]=='b'&&s[2]=='c')
{
printf("aacc");
}
if(s[1]=='a'&&s[2]=='c')
{
printf("abc");
}
if(s[1]=='b'&&s[2]=='c')
{
printf("aa");
getch();
}
}
}
}}}
Check my solution here:
basicalgos.blogspot.com/2012/02/string-reduction-given-string.html
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
using namespace std;
string s;
map<string,int>mp;
map<string,string>change;
int get(string s)
{
int i,j;
int len=s.size();
int ans=len;
if(mp.count(s)!=0)
return mp[s];
for(i=0; i<s.size()-1; i++)
{
string now=s.substr(i,2);
if(change.count(now)!=0)
{
string tp=s.substr(0,i);
string tp1=s.substr(i+2,len-(i+2));
string tp2=change[now];
string next=tp1+tp+tp2;
ans=min(ans,get(next));
}
}
return mp[s]=ans;
}
int main()
{
int i,j,k,t;
freopen("in.txt","r",stdin);
scanf("%d",&t);
for(i=0; i<t; i++)
{
mp.clear();
change["ab"]="c";
change["ba"]="c";
change["ac"]="b";
change["ca"]="b";
change["cb"]="a";
change["bc"]="a";
cin>>s;
int ans;
ans=get(s);
cout<<ans<<endl;
}
}
string reduce (string toReduce)
{
string [] paths = new srtring [6];
string min = toReduce;
path[0] = toReduce.replace('ac', 'b');
path[1] = toReduce.replace('ab', 'c');
path[2] = toReduce.replace('bc', 'a');
path[3] = toReduce.replace('cb', 'a');
path[4] = toReduce.replace('ca', 'b');
path[5] = toReduce.replace('ba', 'c');
for (int i = 0; i < 6; i++)
{
if (path[i] != toReduce)
path [i] = reduce (path[i]);
if (path[i].length < min.length) min = path[i];
}
return min;
}
Solvable with no code. If all three types have either an even or odd number, then the smallest string has size 2. Otherwise 1. Or a special case like he original string is all 1 char which can be treated separately.
To see this consider that e odd/even imbalance is preserved by any combination. If all are even or odd, then a combination switches their mode from all even to all odd or vice versa since the two combined lose 1 and the created char gains one. Similarly an imbalance keeps the imbalance but switches it from odd to even or vice versa.
Thus no combination can ever get you from all odd or even to 1 char left since zero is not odd. This does not fully prove our assertion since it does not prove that all cases are reducible to 2 or 1. That is easily shown by proving that any imbalance is easily reduced to an off by one case e.g. 4/4/5. I leave that up to readers.
char replace(char char1, char char2)
{
if((char1=='a' && char2=='b') || (char1=='b' && char2=='a')) return 'c';
else if((char1=='a' && char2=='c') || (char1=='c' && char2=='a')) return 'b';
else return 'a';
}
int main()
{
string a = "bcabccc";
for(int i=0 ;i+1<a.length(); i++)
{
if(a[i]!=a[i+1])
{
a[i] = replace(a[i],a[i+1]);
a.erase(i+1,1);
i= (i-2<-1)?-1:i-2;
}
cout << a <<" ";
}
cout <<a.length();
int MinOfChars(int *Arr,int PrevSum)
{
if(Arr[0] != 0 && (Arr[1] == 0 && Arr[2] == 0))
return (Arr[0]);
if(Arr[1] != 0 && (Arr[0] == 0 && Arr[2] == 0))
return (Arr[1]);
if(Arr[2] != 0 && (Arr[0] == 0 && Arr[1] == 0))
return (Arr[2]);
int CurrSum = Arr[0] + Arr[1] + Arr[2];
if(PrevSum == CurrSum)
return CurrSum;
sort(Arr,Arr + 3);
Arr[2] -= Arr[1];
Arr[0] += Arr[1];
Arr[1] = 0;
return(MinOfChars(Arr,CurrSum));
}
int MinOfChars(char *S)
{
int Arr[3] = {0,0,0};
for(int i = 0; i < strlen(S); ++i)
{
Arr[S[i] - 'a']++;
}
return MinOfChars(Arr,-1);
}
int MinOfChars(int *Arr,int PrevSum)
{
if(Arr[0] != 0 && (Arr[1] == 0 && Arr[2] == 0))
return (Arr[0]);
if(Arr[1] != 0 && (Arr[0] == 0 && Arr[2] == 0))
return (Arr[1]);
if(Arr[2] != 0 && (Arr[0] == 0 && Arr[1] == 0))
return (Arr[2]);
int CurrSum = Arr[0] + Arr[1] + Arr[2];
if(PrevSum == CurrSum)
return CurrSum;
sort(Arr,Arr + 3);
Arr[2] -= Arr[1];
Arr[0] += Arr[1];
Arr[1] = 0;
return(MinOfChars(Arr,CurrSum));
}
int MinOfChars(char *S)
{
int Arr[3] = {0,0,0};
for(int i = 0; i < strlen(S); ++i)
{
Arr[S[i] - 'a']++;
}
return MinOfChars(Arr,-1);
}
public class StringReduction {
StringReduction() {
}
private int allEqual(String str) {
boolean ret = true;
char pc;
if (str.length() == 1)
return 1;
char[] ca = str.toCharArray();
pc = ca[0];
for (int i = 1; i < ca.length; i++) {
if (ca[i] != pc)
return 0;
pc = ca[i];
}
return ca.length;
}
private String replaceTwo(String str, int i) {
if (str == null)
throw new NullPointerException();
if (str.length() == 1)
return str;
if (str.length() - 1 < i + 1)
return str;// do not replace
char[] ca = str.toCharArray();
char replaceC = '\0';
if (ca[i] == ca[i + 1])
return str;
if (ca[i] == 'a' && ca[i + 1] == 'b') {
replaceC = 'c';
} else if (ca[i] == 'b' && ca[i + 1] == 'c') {
replaceC = 'a';
} else if (ca[i] == 'c' && ca[i + 1] == 'a') {
replaceC = 'b';
}
if (i > 0 && (i + 2) < str.length()) {
return (i > 1) ? str.substring(0, i - 1) + replaceC
+ str.substring(i + 2) : ca[0] + replaceC
+ str.substring(i + 2);
} else if (i == 0 && (i + 2) < str.length()) {
return replaceC + str.substring(i + 2);
} else if (i > 0 && (i + 2) >= str.length()) {
return (i > 1) ? str.substring(0, i - 1) + replaceC : "" + ca[0] + replaceC;
} else if (i == 0 && (i + 2) >= str.length()) {
return replaceC + "";
}
return "";
}
private int min(int a, int b) {
if (a > b)
return b;
else
return a;
}
public int stringReduced(String str, int i) {
if (str.length() == 1)
return 1;
if (this.allEqual(str) > 0 || str.length() == i)
return str.length();
String reduceString = this.replaceTwo(str, i);
int reduceVal = 0;
if (reduceString.equals(str)) {
reduceVal = stringReduced(str, i + 1);
} else {
reduceVal = stringReduced(reduceString, 0);
}
int noreduceVal = stringReduced(str, i + 1);
return min(noreduceVal, reduceVal);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().toString());
for (int i = T; --i >= 0;) {
String S = br.readLine();
if (S.length() < 2) {
System.out.println(S.length());
} else {
process(S);
}
}
}
private static void process(String S) {
for (int i = 0; i < S.length() - 1; i++) {
String temp = S.substring(i, i + 2);
if (temp.contains("ab") || temp.contains("ba")) {
S = S.replaceFirst(temp, "c");
i = -1;
} else if (temp.contains("ac") || temp.contains("ca")) {
S = S.replaceFirst(temp, "b");
i = -1;
} else if (temp.contains("bc") || temp.contains("cb")) {
S = S.replaceFirst(temp, "a");
i = -1;
}
}
System.out.println(S.length());
}
}
#import<stdio.h>
#import<string.h>
char diff(char a, char b)
{
if((a == 'a' && b == 'b') || (a == 'b' && b == 'a'))
return 'c';
else if((a == 'b' && b == 'c') || (a == 'c' && b == 'b'))
return 'a';
else if((a == 'a' && b == 'c') || (a == 'c' && b == 'a'))
return 'b';
else
return '@';
}
void moveZeros(char* a)
{
size_t len = strlen(a);
int index0 = 0;
int indexN = 0;
printf("-->before %s",a);
for(int i = 0; i < len; i++)
{
if(a[i] != '@')
{
int temp = a[i];
a[i] = a[index0];
a[index0] = temp;
index0++;
}
}
a[index0] = '\0';
printf("--> %s",a);
}
void stringCompression(char* str, size_t len)
{
int i = 0;
int j;
int cont = 1;
while(cont == 1){
i = 0;
cont = 0;
for(j = 1; j < len;)
{
char r = diff(str[i], str[j]);
if(r != '@')
{
cont = 1;
str[i] = r;
str[j] = '@';
i++;
}
else
i = j;
j++;
}
moveZeros(str);
}
printf("\t%lu\n",strlen(str));
}
int main()
{
char a[] = "acbb";
char b[] = "aaaabbbb";
char c[] = "aaa";
char d[] = "acacac";
printf("For %s :",a);
stringCompression(a, strlen(a));
printf("For %s :",b);
stringCompression(b, strlen(b));
printf("For %s :",c);
stringCompression(c, strlen(c));
printf("For %s :",d);
stringCompression(d, strlen(d));
}
This code scans the array from left to right, and replaces them.
IN JAVA:
public class StringReduction{
static HashMap<String, String> map = new HashMap<String, String>();
static List<Integer> len = new ArrayList<Integer>();
static{
map.put("ab", "c");
map.put("ba", "c");
map.put("ac", "b");
map.put("ca", "b");
map.put("bc", "a");
map.put("cb", "a");
}
public static void main(String args[]) throws Exception {
reduce("abaaccbca");
Collections.sort(len);
System.out.println(len.get(0));
}
static void reduce(String s){
Object combinations[] = getCombinations(s);
//int count = 0;
for(Object comb : combinations){
if(map.containsKey((String)comb)){
reduce(s.replace((String)comb, map.get((String)comb)));
}
}
len.add(s.length());
}
static Object[] getCombinations(String s){
ArrayList<String> list = new ArrayList<String>();
for(int i = 0;i<s.length()-1; i++){
list.add(s.charAt(i)+""+s.charAt(i+1));
}
return list.toArray();
}
}
}
public void smalleststring(String s) {
int res = s.length();
Queue<String> queue = new LinkedList<String>();
queue.add(s);
while(! queue.isEmpty()) {
s = queue.poll();
char[] ch = s.toCharArray();
if(ch.length == 1 || same(ch)) {
res = Math.min(res, ch.length);
continue;
}
for(int i=0; i<ch.length - 1; i++) {
if(ch[i] != ch[i+1]) {
StringBuilder sb = new StringBuilder();
sb.append(s);
char c = (char) ('a' + (3- (ch[i] + ch[i+1] - 'a' -'a')));
sb.replace(i, i+2, String.valueOf(c));
if (! queue.contains(sb.toString())) {
queue.add(sb.toString());
}
}
}
}
System.out.println("res: "+ res);
}
public boolean same(char[] ch) {
for(int i= 0 ; i <ch.length - 1; i++) {
if(ch[i] != ch[i+1]) {
return false;
}
}
return true;
}
192 1. put chars in a link list ( can use doubly link list)
193 2. p1 = start of list
194 3. p2 = p1->next;
195 4. while (all elements in list become same) {
196
197 while(p2!=NUL){
198 if(p1=>value != p2->value){
199 p2 = p2->next;
200 p2->value = replace with 3rd char
201 del(p2);
202
203 } else {
204 p2 = p2->next;
205 p1 = p1->next;
206 }
207 }
208 }
209
210 5. after the loop ends all chars will be same. get the lenth of link list
211 6. Reverse the orginal link list
212 8. run step 4 on reversed link list
213 9. get the length on the list obtained in step 8
214 10 return the min len of step 5 and 9
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define MAXN 105
char str[MAXN];
int dp[3][MAXN], canDP[MAXN][MAXN][3], vis[MAXN][MAXN][3], cs;
const int INF = 1000000;
inline int min(int u, int v) {return u < v ? u : v;}
bool Can(int st, int ed, char ch)
{
//Can we reduce the substring [st, ed] to a single character ch?
if(st == ed) return (str[st] == ch);
if(vis[st][ed][ch] == cs) return canDP[st][ed][ch];
vis[st][ed][ch] = cs;
int u, v, k;
if(ch == 0) u = 1, v = 2;
if(ch == 1) u = 0, v = 2;
if(ch == 2) u = 0, v = 1;
for(k = st; k < ed; k++)
if( (Can(st, k, u) && Can(k+1, ed, v)) || (Can(st, k, v) && Can(k+1, ed, u)) )
return canDP[st][ed][ch] = true;
return canDP[st][ed][ch] = false;
}
int main()
{
int i, j, tcase;
int len, ch;
scanf("%d", &tcase);
while(tcase--)
{
cs++;
scanf("%s", str + 1);
len = strlen( str + 1);
for(i = 1; i <= len; i++) str[i] -= 'a'; // Replacing a, b & c with 0, 1 & 2.
for(ch = 0; ch < 3; ch++)
for(i = 1; i <= len; i++)
{
dp[ch][i] = INF;
for(j = 1; j <= i; j++)
if( Can(j, i, ch) )
dp[ch][i] = min(dp[ch][i], dp[ch][j-1] + 1);
}
printf("%d\n", min(dp[0][len], min(dp[1][len], dp[2][len])));
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define MAXN 105
char str[MAXN];
int dp[3][MAXN], canDP[MAXN][MAXN][3], vis[MAXN][MAXN][3], cs;
const int INF = 1000000;
inline int min(int u, int v) {return u < v ? u : v;}
bool Can(int st, int ed, char ch)
{
//Can we reduce the substring [st, ed] to a single character ch?
if(st == ed) return (str[st] == ch);
if(vis[st][ed][ch] == cs) return canDP[st][ed][ch];
vis[st][ed][ch] = cs;
int u, v, k;
if(ch == 0) u = 1, v = 2;
if(ch == 1) u = 0, v = 2;
if(ch == 2) u = 0, v = 1;
for(k = st; k < ed; k++)
if( (Can(st, k, u) && Can(k+1, ed, v)) || (Can(st, k, v) && Can(k+1, ed, u)) )
return canDP[st][ed][ch] = true;
return canDP[st][ed][ch] = false;
}
int main()
{
int i, j, tcase;
int len, ch;
scanf("%d", &tcase);
while(tcase--)
{
cs++;
scanf("%s", str + 1);
len = strlen( str + 1);
for(i = 1; i <= len; i++) str[i] -= 'a'; // Replacing a, b & c with 0, 1 & 2.
for(ch = 0; ch < 3; ch++)
for(i = 1; i <= len; i++)
{
dp[ch][i] = INF;
for(j = 1; j <= i; j++)
if( Can(j, i, ch) )
dp[ch][i] = min(dp[ch][i], dp[ch][j-1] + 1);
}
printf("%d\n", min(dp[0][len], min(dp[1][len], dp[2][len])));
}
return 0;
}
#include "algorithm"
#include "iostream"
#include "numeric"
#include "iomanip"
#include "cstring"
#include "math.h"
#include "bitset"
#include "string"
#include "vector"
#include "ctime"
#include "queue"
#include "stack"
#include "map"
#include "set"
#include "ext/pb_ds/assoc_container.hpp" // Common file
#include "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include "ext/pb_ds/detail/standard_policies.hpp"
using namespace std;
using namespace __gnu_pbds;
#define f first
#define lgn 25
#define endl '\n'
#define sc second
#define pb push_back
#define N (int) 200+5
#define PI acos(-1.0)
#define int long long
#define vi vector<int>
#define mod 1000000007
#define ld long double
#define eb emplace_back
#define mii map<int,int>
#define vpii vector<pii>
#define pii pair<int,int>
#define pq priority_queue
#define BLOCK (int)sqrt(N)
#define test(x) while(x--)
#define all(x) begin(x),end(x)
#define allr(x) x.rbegin(),x.rend()
#define fo(i,a,n) for(int i=a;i<n;i++)
#define rfo(i,n,a) for(int i=n;i>=a;i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update >
OS ;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n,m,k,q;
string s;
int dp[N][N]; // dp[i][j] -> minimum length we can formed in interval (i,j)
int val[N][N]; // val[i][j] -> updated value for any interval
// let a -> 1 , b -> 2 and c -> 3
void go()
{
cin >> s;
n = s.size();
s = " " + s;
memset( dp , 0, sizeof dp );
memset( val , 0 , sizeof val );
for( int i = 1; i <= n; i++)
{
for( int j = i; j <= n; j++)
{
if( i == j )
{
if( s[i] == 'a' ) val[i][i] = 1;
if( s[i] == 'b' ) val[i][i] = 2;
if( s[i] == 'c' ) val[i][i] = 3;
}
dp[i][j] = ( j - i + 1); // mark the length
}
}
for(int gap = 1; gap <= n; gap++)
{
for( int i = 1; i + gap <= n; i++)
{
int j = i + gap;
for( int k = i; k < j; k++)
{
dp[i][j] = min( dp[i][j] , dp[i][k] + dp[k+1][j] );
int sum = val[i][k] + val[k+1][j];
if( val[i][k] and val[k+1][j] and val[i][k] != val[k+1][j] and dp[i][j] > 0)
{
if( sum == 3 ) val[i][j] = 3;
if( sum == 4 ) val[i][j] = 2;
if( sum == 5 ) val[i][j] = 1;
dp[i][j] = min( dp[i][j] , max(1LL , dp[i][j] - 1) );
}
}
}
}
cout << dp[1][n] << endl;
}
int32_t main()
{
FAST;
int t=1;
cin>>t;
test(t) go();
}
The smallest we can get is the length of smallest substring formed by similar consecutive elements.
e.g. abcbac ( smallest consecutive is 1 ) so string reduces to size 1.
conside aaaabbbccccc ( a4,b3,c5) it should reduce to 3 since smallest consecutive similar is 3 )
aaaabbbccccc -> aaaabbacccc ->
aaaabbacc -> aaaabccc -> aaacccc -> aabccc -> aaa. (length is 3)
suppose aaa is the given string, if we apply the process repeatedly, it can get reduced to size 1.
aaa->aa->a
I dint get the question.
The string should contain of atleast two of the three characters otherwise your solution won't work either. what if it's just aaa or bbbbbbbbb or cccccc or aaaaaaaaaaa :) still searchinf for a better counter example though. cheers!
take the array with O(n)
Walk through original array and whenever two adjacent character diff replace it and keep the final result in second array
apply the same with second array,
Repeat above procedure unless all elements are same or length equal to 1.
Time O(n^2)
Space O(n)
Space complexity can avoided if be put the result back to original array .
Count the number of occurences of each letter in the input string [numA, numB, numC]
- NaiveCoder February 20, 2012If two of these counts are 0, then return string.length
Else if (all counts are even) or (all counts are odd), then return 2
Else, then return 1