CareerCup

I don't think it's possible if we don't know the indices of the replaced char. Perhaps we could create a kind of proxy around the string and perform the update lazily when the string is requested. Otherwise, it can't be better than O(n), because the worst case requires to modify all the characters.

How can we do it in less than O(n). What if all the n charecters are the same charecter (which is to be replaced).

As pointed out by @Kid of Kop, I doubt a O(n) solution...

Below is a C version of O(n) solution:

void ReplaceChar ( char *str, char Find, char Replace ) {
   while ( *str ) {
        if ( *str == Find )
            *str = Replace ;
        str++ ;
    } 
}

as there is no constraint regarding what character has to be substituted,we just add one to each char,

ex:if i/p is ABCa
o/p wil be BCDB.

I think we can use bitwise operators to mask all non-replaceable characters and then OR with to-be replaced character and then merge back to main string ?

u should have asked interviewer if the string is sorted.
If the given string is sorted then:
Just find the character using binary search and from there start replacing

And how about this :

for(int i=0;i<l/2;i++)
{
   if(a[i]=='character to replace')
     replace it
   elseif(a[l-i]=='character to replace')
    replace it
}

u should have asked interviewer if the string is sorted.
If the given string is sorted then:
Just find the character using binary search and from there start replacing

And how about this :

for(int i=0;i<l/2;i++)
{
   if(a[i]=='character to replace')
     replace it
   elseif(a[l-i]=='character to replace')
    replace it
}

get 2 pointers one to the start and one to end.

while( start != end )
{
if(*start == 'c' || *end == 'c' )
{
code to replace(char);
}
start++;
end--
}

String str = "abcaera";
		char a = 'a';
		char r = 'z';
		char[] chars = str.toCharArray();
		int l = chars.length-1;
		int c = 0;
		for(int i=0; i<=l/2; i++) {
			if(chars[i] == a) {
				chars[i] = r;
			} 
			
			if(chars[l-i] == a) {
				chars[l-i] = r;
			} 
			c++;
		}
		System.out.println("Original String = " + str);
		System.out.println("Replaced String = " + new String(chars));
		System.out.println("Number of interations = " + c);

I dont think its possible in less than O(n) as we have to traverse all the characters of string at least once

If the string was originally sorted, maybe binary search, find the first occurrence of the char and substitute.

Still, the worst case would be O(n) if all the characters in the string are the same as has been pointed out by others.

Also it would need a binary search algorithm with extra storage for values

1) Traverse the string and build binary search data structure with indexes stored as values(in a linked list) - This is only once
2) Write a replace function that would find the search character using binary search and get the index list
3) Traverse the index list and replace the characters at the index location by direct index reference.

Assuming you are allowed to keep track of a list of each character's positions while the string is built, then the best and average case of 'replaceChar()' would be < O(n). What do you guys think?

import java.util.*;

public class HelloWorld {

    static Map<Character, List<Integer>> positions = new HashMap<Character, List<Integer>>();

    public static void main(String []args) {
        String s = buildString('h','e','l','l','o',' ','w','o','r','l','d');
        System.out.println("s: " + s);
        System.out.println(positions);
        s = replaceChar(s, 'l', 'X');
        System.out.println("s: " + s);
    }
    
    static String buildString(char... chars) {
        String s = null;
        for (char c : chars) {
            s = append(s, c);
        }
        return s;
    }
    
    static String append(String s, char c) {
        if (s == null) s = "";
        String newS = s + c;
        List<Integer> charPositions = positions.get(c);
        if (charPositions == null) {
            charPositions = new ArrayList<Integer>();
            positions.put(c, charPositions);
        }
        charPositions.add(newS.length()-1);
        return newS;
    }
    
    static String replaceChar(String s, char c, char newC) {
        List<Integer> charPositions = positions.get(c);
        if (charPositions == null) return s;
        char[] charArr = s.toCharArray();
        for (int pos : charPositions) {
            charArr[pos] = newC;
        }
        return new String(charArr);
    }
}

Output is:

s: hello world
{w=[6], d=[10], =[5], e=[1], r=[8], o=[4, 7], l=[2, 3, 9], h=[0]}
s: heXXo worXd

How abt using Merge sort/binary search concept by diving array into half.....ord( log n).
#include <stdlib.h>
#include <stdio.h>

void replacCharinString( char *cpystr, int i, int j, char *x, char *y){
     
     if( i==j){ if(cpystr[i]== *x) cpystr[i]= *y; return;}
     
     replacCharinString( cpystr,i,(i+j)/2, x,y);
     replacCharinString( cpystr,(i+j)/2+1,j, x,y);
     }

main(){
       int i,count;
       char a,b;
       char str[100];
       printf("enter a string     ");
       scanf("%s",str);
       a=getchar(); // this is used to get rid of "\n" as a character;
       printf("enter a character that u need to replace in given string     ");
       a=getchar();
       b=getchar(); // this is used to get rid of "\n" as a character;
       printf("enter a character that  by which u wnat to replace in given string     ");
       b=getchar();
       i=0;count=0;
       while ( str[i] != '\0'){ i++; count++;}
       replacCharinString( str,0,count-1,&a,&b);
       printf("Replaced string is  %s\n",str);
       
       scanf("%d",&i);
       
       }