Google Interview Question
Software Engineer / DevelopersCountry: Switzerland
Interview Type: Phone Interview
This seems to be fine for this specific problem, but we can't extend this solution to a generic solution using current approach.
we need delete the chars and move the remaining chars in the same iteration
int eliminate( char* p)
{
int deleted = 0;
if ( ! p )
return deleted;
while (*p)
{
if ( *p == 'b' )
deleted++;
else if ( ( *p == 'a' ) && ( *(p+1) == 'c'))
{
deleted += 2;
p++;
} else if ( deleted > 0 )
*(p-deleted) = *p;
p++;
}
return deleted;
}
Check my solution... working perfect with all inputs.
public class removeacAndb {
public static void main(String[] args) {
int k = 0;
int i = 0;
String s = "acbadc";
char[] a = s.toCharArray();
while (i < a.length) {
if (!(a[i] == 'a' && ((a[i + 1] == 'c') && i + 1 < a.length))) {
if (a[i] != 'b') {
a[k] = a[i];
k++;
}
} else
i++;
i++;
}
int p = 0;
while (k > p) {
System.out.print(a[p]);
p++;
}
}
}
Potential bug in the program. program will crash for input "a" because of ( *(p+1) == 'c').
Wrote this python version of your code.
def eliminate(word):
#convert the string to list
str = []
for ch in word:
str.append(ch)
i = 0
pos_to_replace = -1
while i < len(str):
if str[i] == 'b':
pos_to_replace = i
elif str[i] == 'a':
if (i < len(str) - 1) and str[i+1] == 'c':
pos_to_replace = i
i = i+2
continue
elif pos_to_replace >= 0:
str[pos_to_replace] = str[i]
pos_to_replace = pos_to_replace + 1
i = i+1
if pos_to_replace >= 0:
return ''.join(c for c in str[:pos_to_replace]) #back to string
else:
return ''.join(c for c in str) #back to string
Logic is simple:
Take 2 pointers which initially points to the start of the array. Here first one represents the end of string without 'b' and 'ac' and first represents the current scan position.
scan the array from the start to end
if the current characters is 'b' or 'ac', increment only second pointer appropriately
if the current characters is not 'b' and 'ac', swap characters pointed by two pointers and then increment both pointers.
result will be the string from the start of the array to the location pointed by first pointer.
void removeBandAC(char *p, int size)
{
int i = 0;
int j = 0;
while( i < size )
{
if (p[i] == 'b')
{
i++;
}
else if ((p[i] == 'a') && (i+1 < size) && (p[i+1] == 'c'))
{
i += 2;
}
else
{
if (i != J) swap(p[i], p[j]);
i++;
j++;
}
}
p[j] = '\0';
}
you have to replace them in-place with what? I think this too straight forward or am i missing something?
i=0;
start iteration;
if char[i] ='a' Flag=1;
if char[i]='b' remove char[i]; reset Flag=0;
if char[i]='c' and Flag=1; remove char[i] and char[i-1]; reset flag;
if char[i] is any other letter; reset flag;
i++;
Input : x a b c y
Start iteration :
for 'x' : flag = 0
for 'a' : flag = 1
for 'b' : remove b and set flag = 0
for 'c' : nothing since flag is 0
for 'x' : nothing since flag is 0
Your output : xacy
Desired Output : xy
public class ElliminateChars {
public static void main(String[] args) {
char[] ch = "abcacd".toCharArray();
int opArrayIndex, ipArrayIndex;
for (opArrayIndex = 0, ipArrayIndex = 0; ipArrayIndex < ch.length;) {
if (ch[ipArrayIndex] == 'b') {
ipArrayIndex++;
} else if (ch[ipArrayIndex] == 'a' && ch[ipArrayIndex + 1] == 'c') {
ipArrayIndex += 2;
}
ch[opArrayIndex] = ch[ipArrayIndex];
opArrayIndex++;
ipArrayIndex++;
}
for (; opArrayIndex < ch.length; opArrayIndex++) {
ch[opArrayIndex] = ' ';
}
for (opArrayIndex = 0; opArrayIndex < ch.length; opArrayIndex++) {
System.out.print(ch[opArrayIndex]);
}
}
}
static void Eliminate(char[] s)
{
int index = 0;
for (int i = 0; i < s.Length; i++)
{
char c = s[i];
if (c == 'b')
continue;
else if (c == 'a' && i + 1 < s.Length && s[i + 1] == 'c')
{
i++; continue;
}
if (index != i)
s[index] = c;
index++;
}
if (index < s.Length)
{
//compact array
for (int i = index; i < s.Length; i++)
s[i] = '\0';
}
}
void remove_ac_or_b(char* str)
{
unsigned int len = strlen(str);
int curr_pos_to_fill = 0; /* index of char to fill */
int curr_pos_to_check = 0; /* index of char to check */
printf("input: (%s)\n",str);
while (curr_pos_to_check < len)
{
/* if we reached "ac", go 2 chars ahead */
if ((curr_pos_to_check < (len - 1)) &&
(str[curr_pos_to_check] == 'a' && str[curr_pos_to_check+1] == 'c'))
{
curr_pos_to_check += 2;
continue;
}
/* if we reached "b", go 1 char ahead */
if (str[curr_pos_to_check] == 'b')
{
curr_pos_to_check++;
continue;
}
/*
we didn't reach any special char, just fill current fill location with current check location
and then increase them both
*/
str[curr_pos_to_fill] = str[curr_pos_to_check];
curr_pos_to_fill++;
curr_pos_to_check++;
}
/* null terimiate the string */
str[curr_pos_to_fill] = '\0';
printf("result: (%s)\n",str);
}
private static string ReplaceString(char[] toreplace)
{
int totalIndex = toreplace.Count();
int writeIndex = 1;
if (toreplace[0] == 'b')
{
writeIndex = 0;
}
for (int i = 1; i < totalIndex; ++i)
{
if (toreplace[i] == 'b')
{
continue;
}
if (toreplace[i] == 'c')
{
if (toreplace[writeIndex - 1] == 'a')
{
writeIndex--;
continue;
}
}
toreplace[writeIndex] = toreplace[i];
writeIndex++;
}
return new string(toreplace, 0, writeIndex);
}
Logic:
-Traverse array
-check each char for 'a' or 'b'
-in case found 'b' delete it and continue traversing
-in case found 'a' check for next char
-in case after 'a' next char is not 'b' continue
-in case after 'a' next char is 'b' check for this 'b' next char
-in case after 'a' next char is 'b' and 'b's next char is not 'c' then delete 'b' and continue traversing
- in case after 'a' next char is 'b' and 'b's next char is 'c' then delete 'abc' and continue traversing
conclusion:
search for occurrence of 'a' or 'b' in case 'b' comes first delete it or check whether 'abc' pattern is there.... if yes.... delete it.
as mentioned in qus:
Examples:
abc -> ac
ac->''
react->rt
it seems for i/p 'abcd' should be 'd'.... not sure...
Question filler [jeso]'s input required...
public static String removeBAndAC(String s) {
Stack<Integer> stack = new Stack<Integer>();
StringBuffer newString = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i);
switch (currentChar) {
case 'a':
stack.push(i);
break;
case 'b':
break;
case 'c':
if (!(stack.isEmpty())) {
stack.pop();
}
else {
newString.append(currentChar);
}
break;
default:
if (!(stack.isEmpty())) {
stack.pop();
newString.append('a');
}
newString.append(currentChar);
break;
}
}
while (!(stack.isEmpty())) {
stack.pop();
newString.append('a');
}
return newString.toString();
} // End of removeBAndAC()
in Scala solution is simple 4-liner:
def eliminate(s: String) : String = {
def eliminateImpl(s: List[Char]): List[Char] = s match {
case Nil => Nil
case 'a'::'c'::cs => eliminateImpl(cs)
case 'b'::cs => eliminateImpl(cs)
case h::tail => h::eliminateImpl(tail)
}
eliminateImpl(s.toList).mkString
}
private static char[] eliminateChar(char[] input) {
int len = input.length, i=0;
for(i=0; i<len; i++) {
if(input[i] == 'b'){
input[i] = ' ';
}
else if(input[i] == 'a' && i+1 < len && input[i+1] == 'c') {
input[i] = input [i+1] = ' ';
}
}
return input;
}
char *str = "aaabbcccbaxc";
std::vector<char> myVector;
for (int i = 0; i < strlen(str); i++)
{
if(str[i] == 'c')
{
if(!myVector.empty())
{
if(myVector.back() == 'a')
myVector.pop_back();
else
myVector.push_back(str[i]);
}
}
else if(str[i] != 'b')
myVector.push_back(str[i]);
}
int i;
char *str2 = new char[myVector.size() + 1];
for ( i = 0; i<myVector.size(); i++)
str2[i] = myVector[i];
str2[i] = '\0';
public static void Eliminate (String[] strIn){
List<String> list = new ArrayList<String>(Arrays.asList(strIn));
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("b")){
list.remove(i);
i--;
} else if ((list.get(i).equals("a")) && (i+1) < list.size())
{
if ((list.get(i+1).equals("c"))) {
list.remove(i+1);
list.remove(i);
i--;
}
}
}
System.out.println(list);
}
I think this code should solve this problem..
public static String eliminate(String data){
char[] strArr = data.toCharArray();
int len = strArr.length;
int i = 0 ;
while(len>0){
if(strArr[i]=='b')
strArr[i]= ' ';
if( i<data.length() && strArr[i]== 'a' && strArr[i+1]=='c')
strArr[i] = strArr[i+1] = ' ';
i++;
len--;
}
return new String(strArr);
}
Pure c style
void removeBAndAC(char * str)
{
int size = strlen(str);
int cur =0; // always wait for available content to copy over;
int rear =0;
while(rear < size)
{
if( !(str[rear] == 'b') && !(rear!= size-1&&str[rear]=='a'&&str[rear]=='c') )
{
str[cur] = str[rear];
cur++;
}
else if( rear != size -1 && str[rear] =='a' && str[rear+1] == 'c' )
{
rear++;
}
rear++;
}
str[cur] = '\0'; // ends at here since no more content to be copied over;
}
public static char[] replace_b_ac(char[] array) {
int j = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] != 'b') {
if (array[i] == 'c' && j > 0 && array[j - 1] == 'a') {
j--;
} else {
array[j] = array[i];
j++;
}
}
}
for (int k = j; k < array.length; k++) array[k] = '\0';
return array;
}
This can be achieved in O(n)
private String remove(String s) {
StringBuilder temp = new StringBuilder();
int len = s.length();
for(int i=0;i<len;i++) {
if((s.charAt(i) != 'b') && (s.charAt(i) != 'a')) {
temp.append(s.charAt(i));
}
if(s.charAt(i) == 'a') {
if(s.charAt(i+1) == 'c') {
i++;
} else {
temp.append(s.charAt(i));
}
}
}
return temp.toString();
}
/*Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
Examples:
abc -> ac
ac->''
react->rt*/
#include<stdio.h>
int move=0;
int checkOut(int aPt,char *str)
{
int i,x=0,j;
for(i=aPt+1;i<strlen(str);i++)
{
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
printf("%d %s\n",aPt,str);
if(str[j+1]=='c')
{
move+=2+x;
str[j-x]=str[j+2];
}
return i;
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
return i;
}
else
return i;
}
}
int main()
{
char str[50];
int i,j,x=0;
scanf("%s",str);
for(i=0;i<strlen(str);i++)
{
printf("%d %d %s\n",i,move,str);
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
if(str[j+1]=='c')
{
move+=2+x;
if(j+2!=strlen(str))
str[j-x]=str[j+2];
}
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
}
else
str[i-move]=str[i];
}
str[strlen(str)-move]='\0';
printf("%d %s\n",move,str);
}
/*Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
Examples:
abc -> ac
ac->''
react->rt*/
#include<stdio.h>
int move=0;
int checkOut(int aPt,char *str)
{
int i,x=0,j;
for(i=aPt+1;i<strlen(str);i++)
{
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
printf("%d %s\n",aPt,str);
if(str[j+1]=='c')
{
move+=2+x;
str[j-x]=str[j+2];
}
return i;
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
return i;
}
else
return i;
}
}
int main()
{
char str[50];
int i,j,x=0;
scanf("%s",str);
for(i=0;i<strlen(str);i++)
{
printf("%d %d %s\n",i,move,str);
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
if(str[j+1]=='c')
{
move+=2+x;
if(j+2!=strlen(str))
str[j-x]=str[j+2];
}
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
}
else
str[i-move]=str[i];
}
str[strlen(str)-move]='\0';
printf("%d %s\n",move,str);
}
/*Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
Examples:
abc -> ac
ac->''
react->rt*/
#include<stdio.h>
int move=0;
int checkOut(int aPt,char *str)
{
int i,x=0,j;
for(i=aPt+1;i<strlen(str);i++)
{
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
printf("%d %s\n",aPt,str);
if(str[j+1]=='c')
{
move+=2+x;
str[j-x]=str[j+2];
}
return i;
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
return i;
}
else
return i;
}
}
int main()
{
char str[50];
int i,j,x=0;
scanf("%s",str);
for(i=0;i<strlen(str);i++)
{
printf("%d %d %s\n",i,move,str);
if(str[i]=='b')
x++;
else if(str[i]=='a')
{
j=i;
i=checkOut(i,str);
if(str[j+1]=='c')
{
move+=2+x;
if(j+2!=strlen(str))
str[j-x]=str[j+2];
}
}
else if(str[i]=='c')
{
str[i-x]='c';
move+=x;
}
else
str[i-move]=str[i];
}
str[strlen(str)-move]='\0';
printf("%d %s\n",move,str);
}
public static void main(String[] args) {
char []arr = {'r','b','x','y','c','c','c'};
int j=-1;
for(int i=0;i<arr.length;i++){
if(arr[i]=='b'){
// arr[j]=arr[i+1];
continue;
}
if(arr[i]=='c' && arr[j]=='a'){
j-=1;
continue;
}
j+=1;
arr[j]=arr[i];
}
System.out.println("Final length is:"+(j+1));
for(int i=0;i<=j;i++){
System.out.print(arr[i]+",");
}
}
public class removeacAndb {
public static void main(String[] args) {
int k = 0;
int i = 0;
String s = "acbadc";
char[] a = s.toCharArray();
while (i < a.length) {
if (!(a[i] == 'a' && ((a[i + 1] == 'c') && i + 1 < a.length))) {
if (a[i] != 'b') {
a[k] = a[i];
k++;
}
} else
i++;
i++;
}
int p = 0;
while (k > p) {
System.out.print(a[p]);
p++;
}
}
}
use two pointer char * write and char * scan, write points to the position to write, whereas scan points to the position to scan.
#include <iostream>
#include <string>
#include <memory>
#include <cstring>
void remove(char * str){
char * write = str;
char * scan = str;
while (*scan != '\0') {
if (*scan == 'b')
++scan;
else if (*scan == 'a' && *(scan+1) == 'c')
scan += 2;
else
*write++ = *scan++;
}
*write = '\0';
}
void test_remove_ac_or_b(){
std::string str;
while(true) {
std::getline(std::cin,str);
std::shared_ptr<char> s(new char[str.size()+1]);
strcpy(s.get(), str.c_str());
std::cout << s.get() << std::endl;
remove(s.get());
std::cout << s.get() << std::endl;
}
}
I was thinking about different solutions but didn't find any one of them generic for all such problems, so writing this solution of mine. I am planning to use a TRIE tree. Will create an TRIE tree using all pairs which can be replaced like b -> "" and ac ->"". TRIE will be something like
node
/ \
b a
\
c
Now we will start with our main string which is rabct
1. start pointer points to r and tries to find it in TRIE tree's first node, but no such thing is there
2. Then increment pointer and move to a, which is present in tree.
3. Move to b and try to find b in child tree of a, but no such thing is there. In this case we need to move to next node to a, which is b.
4. Search b in tree and we find it, now as next node of b is null, means we have our b and delete it from tree. But now there exist a pattern which start before b, so once we find a pattern, we start from current node - (height of TRIE tree - 1), which is 2 in our case, so move back to (node was b at 3rd node - 2 height of tree -1) which is again a.
5. Search a in TRIE and we have it.
6. Move to next node which is c (as b is deleted), search for c, which is there so delete ac, then move back to r.
7. Check for r, then move ahead and check for t. Then we are done.
In this case we assumed that everything will end up in "", but we can replace it with some different value by putting it at last node of TRIE tree for each path. This way we can make this solution generic and independent of whatever is given to us. As per my understand, complexity is O(n^m) where n is number of pattern and m is length of test string
Please give your valuable feedback.
// Replacing ac and b with blank. Once done, splitting, merging and converting to char[] again.
for(int i=0,j=-1;i<arr.length;i++){
switch(arr[i]){
case 'a' : j=i;
break;
case 'c' : if(j!=-1){
arr[j--] = ' ';
arr[i] = ' ';
}
break;
case 'b' : arr[i] = ' ';
break;
default : j=-1;
break;
}
}
String result = "";
for(String s : (new String(arr).split(" ")))
result = result + s;
arr = result.toCharArray();
for(char c : arr)
System.out.print(c+" ");
hi, please check this piece of code. If there is any issue in this
public class eliminatebAndac {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
fneliminatebAndac("rebtacd");
}
public static void fneliminatebAndac(String s){
String result="";
System.out.println(s.length());
for (int i=0;i<s.length();){
if(i==s.length()-1){
if(s.charAt(i)=='b'){
continue;
}
else{
result=result+(s.charAt(i));
break;
}
}
else if((s.charAt(i)=='b')){
i=i+1;
}
else if( (""+s.charAt(i)+s.charAt(i+1)).equals("ac")){
i=i+2;
}
else {
result=result+(s.charAt(i));
i=i+1;
}
}
System.out.println(result);
}
}
#include<stdio.h>
void edit(char *str);
int main()
{
char str[20]="bacbacapplebbac";
edit(str);
printf("%s\n",str);
}
void edit(char *str)
{
int i=0;
char *temp=str;
while(*temp)
{
if(*temp=='b')
temp++;
else
{
if(*temp=='a'&&(*(temp+1)=='c'))
{
temp=temp+2;
}
else
{
str[i]=*temp;
temp++;i++;
}
}
}
str[i]='\0' ;
}
Using in-place stack - this is the only right solution and it actually works!
public static String removeBAndAC(String s)
{
char[] str = s.ToCharArray();
int t = -1;
for (int i = 0; i < str.Length; i++)
{
t++; // push char
str[t] = str[i];
int tt; // temp var to see if we are done poping
do
{
tt = t;
if (str[t] == 'b') t -= 1; // pop 'b', if needed
else if (t >= 1 && str[t - 1] == 'a' && str[t] == 'c') t -= 2; // pop 'ac', if needed
}
while (tt != t); // keep going while there was stuff to pop out
}
s = new String(str.Take(t+1).ToArray());
Console.WriteLine(s);
return s;
}
removeBAndAC("zaabccbxabyzc"); // returns "zxayzc"
#include <iostream>
using namespace std;
int main()
{
char s[] = "adaabunhaccc";
int p, i, l;
l = strlen(s);
i = 0;
p = -1;
while(i < l)
{
if(s[i] == 'b')
s[i] = '\0';
else if(s[i] == 'a' && s[i + 1] == 'c')
{
s[i] = s[i + 1] = '\0';
++i;
}
else if(s[i] == 'c')
{
if(s[p] == 'a')
{
s[i] = s[p] = '\0';
--p;
}
else
s[++p] = s[i];
}
else
s[++p] = s[i];
++i;
}
s[++p] = '\0';
cout << s << endl;
}
Simple java implementation
public static char[] removeBandAC(char[] chars)
{
int i = 0, r = 0, n = chars.length;
while (i < n)
{
if (chars[i] == 'b')
{
// do nothing
}
else if (chars[i] == 'a' && i < n - 1 && chars[i + 1] == 'c')
{
i++;
}
else
{
chars[r] = chars[i];
r++;
}
i++;
}
while (r < n)
{
chars[r] = '\0';
r++;
}
return chars;
}
#include <iostream>
using namespace std;
void stringFilter(char *str)
{
int i,j=0;
for(i=0;str[i]!='\0';)
{
if(str[i] =='b'){
i++;
continue;
}
else if(str[i]=='a' && str[i+1] == 'c'){
i+=2;
continue;
}
str[j++] = str[i++];
if(j>1 && str[j-2]=='a' && str[j-1] == 'c')
j-=2;
}
str[j] = '\0';
}
int main()
{
char str1[] = "abbbbd";
stringFilter(str1);
cout << str1 << endl;
char str2[] = "acbac";
stringFilter(str2);
cout << str2 << endl;
char str3[] = "aaac";
stringFilter(str3);
cout << str3 << endl;
char str4[] = "react";
stringFilter(str4);
cout << str4 << endl;
char str5[] = "aa";
stringFilter(str5);
cout << str5 << endl;
char str6[] = "ababaac";
stringFilter(str6);
cout << str6 << endl;
char str7[] = "aacacc";
stringFilter(str7);
cout << str7 << endl;
char str8[] = "aacaccd";
stringFilter(str8);
cout << str8 << endl;
return 0;
}
simple O(n) implementation
#include <iostream>
using namespace std;
void stringFilter(char *str)
{
int i,j=0;
for(i=0;str[i]!='\0';)
{
if(str[i] =='b'){
i++;
continue;
}
else if(str[i]=='a' && str[i+1] == 'c'){
i+=2;
continue;
}
str[j++] = str[i++];
if(j>1 && str[j-2]=='a' && str[j-1] == 'c')
j-=2;
}
str[j] = '\0';
}
int main()
{
char str1[] = "abbbbd";
stringFilter(str1);
cout << str1 << endl;
char str2[] = "acbac";
stringFilter(str2);
cout << str2 << endl;
char str3[] = "aaac";
stringFilter(str3);
cout << str3 << endl;
char str4[] = "react";
stringFilter(str4);
cout << str4 << endl;
char str5[] = "aa";
stringFilter(str5);
cout << str5 << endl;
char str6[] = "ababaac";
stringFilter(str6);
cout << str6 << endl;
char str7[] = "aacacc";
stringFilter(str7);
cout << str7 << endl;
char str8[] = "aacaccd";
stringFilter(str8);
cout << str8 << endl;
return 0;
}
simple O(n) implementation
#include <iostream>
using namespace std;
void stringFilter(char *str)
{
int i,j=0;
for(i=0;str[i]!='\0';)
{
if(str[i] =='b'){
i++;
continue;
}
else if(str[i]=='a' && str[i+1] == 'c'){
i+=2;
continue;
}
str[j++] = str[i++];
if(j>1 && str[j-2]=='a' && str[j-1] == 'c')
j-=2;
}
str[j] = '\0';
}
int main()
{
char str1[] = "abbbbd";
stringFilter(str1);
cout << str1 << endl;
char str2[] = "acbac";
stringFilter(str2);
cout << str2 << endl;
char str3[] = "aaac";
stringFilter(str3);
cout << str3 << endl;
char str4[] = "react";
stringFilter(str4);
cout << str4 << endl;
char str5[] = "aa";
stringFilter(str5);
cout << str5 << endl;
char str6[] = "ababaac";
stringFilter(str6);
cout << str6 << endl;
char str7[] = "aacacc";
stringFilter(str7);
cout << str7 << endl;
char str8[] = "aacaccd";
stringFilter(str8);
cout << str8 << endl;
return 0;
}
void function(string& str)
{
int pos = 0;
for(int i=0;i<str.length()-1;i++)
{
if(str[i] == 'b')
continue;
else if(str[i] == 'a' && str[i+1] == 'c')
{
i += 1;
continue;
}
if(i < str.length()-1)
str[pos++] = str[i];
}
if(!(str[str.length()-1] != 'b' || (str[str.length()-2] != 'a' && str[str.length()-1] != 'c')))
str[pos++] = str[str.length()-1];
for(int i=0;i<pos;i++)
cout<<str[i];
cout<<endl;
}
// Eliminate all 'b' and 'ac'.cpp : Defines the entry point for the console application.
// Program to eliminate all "b" and "ac" in a string
#include<iostream>
int main()
{
char szStr[] = "abcbac";
int i = 0;
int j = 0;
while (szStr[j])
{
if (szStr[j] == 'b' || (szStr[j] == 'a' && szStr[j + 1] && szStr[j + 1] == 'c'))
{
if (szStr[j] == 'a')
{
j++;
}
}
else
{
if (i != j)
{
szStr[i] = szStr[j];
}
i++;
}
j++;
}
szStr[i] = '\0';
std::cout << "String after removing b and ac is " << szStr << std::endl;
return 0;
}
#include<iostream>
int main()
{
char szStr[] = "abcbac";
int i = 0;
int j = 0;
while (szStr[j])
{
if (szStr[j] == 'b' || (szStr[j] == 'a' && szStr[j + 1] && szStr[j + 1] == 'c'))
{
if (szStr[j] == 'a')
{
j++;
}
}
else
{
if (i != j)
{
szStr[i] = szStr[j];
}
i++;
}
j++;
}
szStr[i] = '\0';
std::cout << "String after removing b and ac is " << szStr << std::endl;
return 0;
}
/**
*
* Eliminate all ‘b’ and ‘ac’ in an array of characters, you have to replace them in-place, and you are only allowed to iterate over the char array once.
*
* Examples:
* abc -> ac
* ac->''
* react->rt
*
*/
public class ReplaceCharacters {
private final String[] charPool = new String[]{"abc", "ac", "react", "actuator", "bubble"};
public void replaceCharArray() {
String selectedStr = charPool[2];
// eliminate the 'ac's first to avoid having to end up with 'ac' that had 'b' in between
char[] chars = selectedStr.replaceAll("ac", "").toCharArray();
StringBuilder stringBuilder = new StringBuilder();
for (int index = 0; index < chars.length; index++) {
if (chars[index] != 'b')
stringBuilder.append(chars[index]);
}
chars = stringBuilder.toString().toCharArray();
// an optional output loop
System.out.println("Output: ");
for (char ch : chars) {
System.out.print(ch);
}
}
}
It can be solved using two pointers thats it :-)
- Arunkumar Somalinga May 18, 2013