A String Replacement Problem

Replace all occurrence of the given pattern to ‘X’.
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.

First, it is not clear whether the problem mentions an in-place replacement or not, so be sure to ask this question during an interview. Many interview questions asked are purposely ambiguous. It is expected that the candidate ask thought-provoking questions of the interviewer in order to better answer the question. Here, we will assume that it is an in-place replacement.

Hint:
If the problem seemed overly complex to you, you are in the wrong path. Try to break the problem into manageable pieces. Consider having a helper function called

bool isMatch(char *str, const char *pattern)

which returns true if pattern matches str starting from its first character.

Solution:
We should take advantage that the replacement is only one character in length. Assume that the pattern is at least one character in length, then the replacement’s length will never exceed the pattern’s length. This means that when we overwrite the existing string with replacement, we would never overwrite characters that would be read next.

Two pointers are also used for an efficient in-place replacement, which traverses the string once without any extra memory.

Test Cases:

Format is string, pattern = answer)
-----------------------------------
a, a = X
aa, aa = X
aa, a = X
aa, aaa = aa
abc, abc = X
abcabc, abc = X
abcabcabc, abc = X
abcaabcaabc, abc = XaXaX
abcaaabcaaabca, abc = XaaXaaXa
abcabcabababcabc, abc = XababX
abcabcabababcabcab, abc = XababXab
aabbaabbaaabbbaabb, aabb = XaXbX
aabbaabbaaabbbaabb, aaabb = aabbaabbXbaabb
aabbaabbaaabbbaaabb, aaabb = aabbaabbXbX
aabbaabbaaabbbaaabc, aaabb = aabbaabbXbaaabc
abcdeffdfegabcabc, abc = XdeffdfegX
abcdeffdfegabcabc, ab = XcdeffdfegXcXc
abcdeffdfegabcabc, a = XbcdeffdfegXbcXbc
abcdeffdfegabcab, abc = XdeffdfegXab
abcdeffdfegabcabcab, abc = XdeffdfegXab
abcdeffdfegabcaabcab, abc = XdeffdfegXaXab
abcdeffdfegabcaaaabcab, abc = XdeffdfegXaaaXab
aaaaaa, a = X
aaaaaa, aa = X
aaaaaa, aaaaaa = X
aaaaaa, aaaaaaa = aaaaaa
aabaababaaab, a = XbXbXbXb
aabaababaaa, a = XbXbXbX
aaaab, a = Xb
baaa, a = bX
aabaaabaab, aaa = aabXbaab
aabaaabaab, aa = XbXabXb
aabaaabaa, aa = XbXabX
VN:F [1.9.22_1171]
Rating: 4.9/5 (10 votes cast)
A String Replacement Problem, 4.9 out of 5 based on 10 ratings

33 thoughts on “A String Replacement Problem

  1. 1337c0d3r

    "in-place" replacement means the string that's passed in the function is being modified and replaced. On the other hand, without "in-place" replacement, the original string would not be modified and you would allocate extra memory to hold the new replaced string and return it at the end of the function.

    VA:F [1.9.22_1171]
    0
  2. Anonymous

    The solution takes care of in-place replacement well. However, the runtime is O(n*m), where n=len(str) and m=len(pattern). It should be easily modified to use KMP algorithm (http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm) to achieve O(n+m). Just replace
    if (*pFast != ”) *pSlow++ = *pFast++; // *p++ = (*p)++
    with
    int i = pFast – str;
    while(*pFast && pFast < str + T[i]) *pSlow++ = *pFast++;
    This will make sure each char in str is compared only once and make the search O(n). Table building requires O(m) so it will be O(n+m).

    VA:F [1.9.22_1171]
    0
  3. Anonymous

    Sorry the algorithm to adopt KMP in the previous post is not correct. isMatch need to be modified to return i which is the index of the first mismatch char in pattern. Then
    pNext = pFast + i – T[i];
    while(*pFast && pFast < pNext) *pSlow++ = *pFast++;

    VA:F [1.9.22_1171]
    0
  4. SkyWalker

    W/ every iteration of the “while(*pFast ! = ”)” you seem to be setting the boolean match to false.

    How will this help in knowing in solving the last part of the problem statement:
    Note, that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’

    Because match is going to be false w/ every loop it will continue matching contiguous characters which match the pattern.

    Thanks.

    VA:F [1.9.22_1171]
    0
  5. Pingback: A Microsoft String Replacement Problem | 口├人人│의 Blog

  6. slimboy

    your solution does not replace multiple occurrences of a pattern by a single ‘X’. However there is still a bug with the current solution which is supposed to do

    string = abcabc, pattern = abc, answer = XX

    This bug can be corrected by making the last step of the loop condition this way

    VA:F [1.9.22_1171]
    0
    1. Ashwin Pednekar

      Even ur change doesnt give the correct answer I hav compiled and seen.
      The code written above is correct , just there is a small bracket error. The
      if(matched) condintion should come inside the inner while loop.
      See here:
      while (isMatch(pFast, pattern)) {
      matched = true;
      pFast += pLen;

      if (matched)
      *pSlow++ = ‘X’;
      }

      VN:F [1.9.22_1171]
      0
  7. Pingback: Unique Path | 口├人人│의 Blog

  8. amit

    It does replace multiple occurences.

    An improvement can be made when we modify the isMatch() such that it compares from the end. And, in case of a mismatch, it also returns the index of patteren where it failed to match.
    In addition, we can add a function that gives the length to skip even in the case of mismatch. This length can be used to skip pFast by more than one character even in case of failure to match the entire pattern. Longer pattern case will be benefited heavily.
    This is simplified Boyer moore Algorithm.
    Thanks.

    VN:F [1.9.22_1171]
    0
  9. Moussa

    I think all parts are correct except the “if” at the end. My version is:
    /*******/

    if (match) *pSlow++ = ‘X’;
    else *pSlow++ = *pFast++;

    /*******/

    Case 1:if there is no match, then *pSlow++ = *pFast++ will work.
    Case 2:if there is a match, pFast should be already in the right position by having pFast += pLen above. And testing *pLast!=” twice seems unnecessary.

    VA:F [1.9.22_1171]
    0
  10. opoopo

    A possible non in-place solution, we can use backtracking

    VA:F [1.9.22_1171]
    0
    1. Prateek Caire

      R()
      if(*str == NULL || *pattern == NULL)
      return
      f = 0
      s = 0
      pLen = strlen(p)
      while(*f != ”)
      bl = false
      while(M(f))
      bl = true
      f = f + len
      if(bl)
      p = pattern
      while(p != ”)
      *s++ = *p++
      if(f != ”)
      *s++ = *f++
      [\code]

      VA:F [1.9.22_1171]
      0
    2. Prateek Caire

      VA:F [1.9.22_1171]
      0
  11. Anonymous

    In case the pattern is an empty string, i.e.,

    your code will have a dead loop because pLen is 0 and the pointer pFast will never move.

    VA:F [1.9.22_1171]
    0
  12. Punit

    The code that can handle every case with consideration of KMP pattern matching

    {{{
    void prepare_table(char* pattern, int *table, int size){
    int prev = 0, curr = 1;
    while(curr 0)
    prev = table[prev-1];
    else{
    table[curr] = table[prev];
    curr++;
    }
    }
    }
    }

    void KMP_replace(char *str, char *pattern){

    char *pFast = str, *pSlow = str, *text_ptr, *pattern_ptr;
    int patternLen = strlen(pattern);
    int *table = new int[patternLen+1](), counter = 0;
    bool matched;
    prepare_table(pattern, table, patternLen+1);
    while(*pFast){
    pattern_ptr = pattern;
    matched = true;
    text_ptr = pFast;
    counter = 0;
    // try to match pattern
    while(*pattern_ptr){
    if(*pattern_ptr++ != *text_ptr++){
    matched = false;
    break;
    }
    counter++;
    }

    if(matched){
    *pSlow++ = ‘X’;
    pFast += patternLen;
    } else{
    // skip number of characters to probe for matching according to KMP
    for(int i = 0; i < (counter ? counter – table[counter] : 1); i++)
    *pSlow++ = *pFast++;
    }
    }
    *pSlow = '';
    }
    }}}

    VA:F [1.9.22_1171]
    0
  13. Pingback: [LeetCode] A String Replace Problem - 编程语言 - 开发者第2269624个问答

  14. Pingback: [LeetCode] A String Replace Problem - 编程 - 开发者

  15. Pingback: LeetCode | techinterviewsolutions

  16. Loki

    The given solutions wont work if the len(replacement string) > len(pattern).
    In that case it is not even clear.. that the problem can be solved inplace…

    The problem will become interesting if lets say the provided array contains enough space to accommodate the final string. Then if we try to solve this inplace, with minimal number of comparisons/shifts.. that would be an interesting problem to solve..

    VN:F [1.9.22_1171]
    0
  17. Pingback: Microsoft Interview | Rachel's Technique and Study Blog

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*