Monday, March 5, 2012

String Reduction

Problem:  A string that only contains three types of letters :"a", "b", "c". Our goal is to reduce the string. If two different letters are adjacent to each other, we can reduce the two letters into another letter. The rule is like this: if we encounter "ab" (or "ba"), we reduce to "c";   if we encounter "bc" (or "cb"), we reduce to "a";  if we encounter "ca" (or "ac"), we reduce to "b". If two adjacent letters are the same, we can't reduce them. We need to find an optimal way to reduce the string as much as possible.

For example, for string "acbb", if we try to reduce "ac"first, we get "bbb". But, if we reduce "cb" first, we get "aab" and we can further make "aab" => "ac" => "b". The latter approach gives us an optimal reduction.

Solution: Here what really matters is the numbers of letter "a", "b" and "c". Let us name them as num_a, num_b and num_c. If two of them are zero, we can't reduce that string. Otherwise, we can reduce the string into a string that has a length of 1 or 2. If num_anum_b and num_c are all even or odd,  we can reduce to a string with length 2; If not, we can reduce to a string with length 1.

Then how to do the reduction? The detail is as follow:

  1. if the string has a length of 3 and contains one "a", one "b" and one "c", whatever order of the three letter are in, we can only reduce the string into a string with length 2; if the string has a length of 2 and contains two different letters, we can only reduce the string into a string with length 1. Let us regard these two cases as base cases.
  2. for a general case, we have num_a "a" num_b  "b" and num_c  "c". After every reduction, the sum of num_anum_b and num_c will decrease by 1, since we substitue two letters with one letter.  
  3. Then at each round, which two adjacent letters we choose to reduce? We try to find an adjacent pair that contains a letter which has the highest count. For example, if now, we have 3 "a", 4 "b" and 6 "c" in the string, we choose an adjacent pair that contains "c"since num_c = max(num_anum_bnum_c) . Can we find such pair? definitely we can. If there are multiple such pairs, choose a random one. Then after we reduce this pair, num_c--, max(num_anum_bnum_c) may decrease by 1, remain unchanged, or increase by 1. However, since max(num_anum_bnum_c) is up-bounded by num_a + num_b num_c. num_a + num_b num_c is decreasing after every round, then max(num_anum_bnum_c) will also decrease if we look at a long wrong. Therefore, by using our strategy,  max(num_anum_bnum_c) will eventually decrease to 1, which means we are encounter the base cases in step 1.
  4. Then when the string will be reduced to a length of 1 and when to a length of 2? We observe that is num_anum_b and num_c are all even, then after one transformation, they will become all odd; similarly, if there are originally all odd, after one transformation, they will become all even. Then according to the analysis in step 3), we know at the end, the max(num_anum_bnum_c) will eventually decrease to 1. But, they should still be all odd at that time (since "1" is odd). Therefore, at the very end, we will have num_a = 1, num_b = 1 and num_c =1, which will  eventually lead to a string of length 2. It is easy to prove that if num_anum_b and num_c are  not all even or odd, the string will be reduced to length 1.
  5. if num_anum_b and num_c are  not all even or odd, there must be only two cases: a) two of the counters are odd and one is even b) two of the counters are even and one is odd.  For example, if num_b is odd, num_a and num_c are both even. The string actually will eventually be reduced to  "b".
  6. if num_anum_b and num_c are all even or odd, there might be multiple different final forms.

11 comments:

  1. Oukay... but can u tell me if i use deque implementation for this solution then for which test cases the solution wont work..

    ReplyDelete
  2. I am not sure about what your deque implementation looks like. The solution described in the post only need to know num_a, num_b and num_c. Then you can know the length of the string after reduction.

    If you want to know what the final string looks like, you may need deque. But, sometimes, you may not be able to covert two characters into one at the very end of the string. If you can paste your implementation here, I can take a look and answer you concern...

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Oukay now u can do this problem through 2 reasonable methods one is backtracking i.e. goin through array recursively using for loop(dont think about implementation) and other is using deque. But since space and time overhead in deque is much less i used it but it wont give answer for some test cases. Here the implementation. Quite an easy one though

    #include
    #include
    using namespace std;
    void checkl(deque &d)
    {
    deque::iterator it;
    it=d.end()-1;
    while(d.size()>1)
    {
    //cout<<*it<<" it "<<*(it-1)<<"\n";
    if(((*it=='a')&& (*(it-1)=='b'))||
    ((*it=='b')&& (*(it-1)=='a')))
    {
    d.pop_back();
    d.pop_back();
    d.push_back('c');
    }
    else if(((*it=='b')&& (*(it-1)=='c'))||
    ((*it=='c')&& (*(it-1)=='b')))
    {
    d.pop_back();
    d.pop_back();
    d.push_back('a');
    }
    else if(((*it=='c')&& (*(it-1)=='a'))||((*it=='a')&& (*(it-1)=='c')))
    {
    d.pop_back();
    d.pop_back();
    d.push_back('b');
    }
    else //if(*it==*(it-1))
    {
    return;
    //cout<<"equal";
    }
    --it;
    }
    }

    void checkr(deque &d)
    {
    deque::iterator it;
    it=d.begin();
    while(d.size()>1)
    {
    if(((*it=='a')&& (*(it+1)=='b'))||
    ((*it=='b')&& (*(it+1)=='a')))
    {
    d.pop_front();
    d.pop_front();
    d.push_front('c');
    }
    else if(((*it=='b')&& (*(it+1)=='c'))||
    ((*it=='c')&& (*(it+1)=='b')))
    {
    d.pop_front();
    d.pop_front();
    d.push_front('a');
    }
    else if(((*it=='c')&& (*(it+1)=='a'))||
    ((*it=='a')&& (*(it+1)=='c')))
    {
    d.pop_front();
    d.pop_front();
    d.push_front('b');
    }
    else //if(*it==*(it+1))
    return;
    ++it;
    }

    int main()
    {
    deque d;
    int i,l,r,min;
    string a;
    cin>>a;

    for(i=0;i=0)
    {
    d.push_back(a[l]);
    checkl(d);
    l--;
    }
    r=i+1;
    while(r<a.length())
    {
    d.push_front(a[r]);
    checkr(d);
    r++;
    }
    if(d.size()<min)
    min=d.size();
    d.clear();
    }
    cout<<min;
    return 0;
    }

    The code works fine as such to compute the minimal string obtained by reduction but for some test cases it fails y so?

    ReplyDelete
    Replies
    1. I see what you are trying to achieve here, but it is not easy for me to help you since it seems the code can't be compiled. You might miss some "{" or "}" (or you might have extra "}"). There are also some problem in main(). Those integers, "l", "r" and "min" are not initialized. It will be a good habit to initialized since sometimes they will let you down. Try to paste the code that can be compiled on any compiler (e.g., gcc/g++).

      Besides, the approach you are taking may not work. You are trying to do is to reduce from both ends. But if you encounter a string like "aabcaa", you may get stuck (or I misread your code). Previously, I had an implementation which can return not only the length of the reduced string, but also the exact reduced string. I don't have the implementation right now but I remember I implemented in a different way.

      Delete
    2. Sir,
      I pasted it correctly actually the formatting in the blogspot took it formatting away. I keep solving on interviewstreet.com so my code worked there but only for 7 out of 10 test cases. What you must have implemented must be the backtracking thing i.e.
      in a recursive manner something similar to below.
      Rough code

      func(ar)
      {
      for(i=0;i<ar.length();i++)
      {
      if(ar[i]!=ar[i+1])
      {
      s=reduce(ar[i],ar[i+1)
      ar=strcat(ar[0 to i],s,ar[i+2 to n]
      func(ar);
      }
      }
      }

      If u want to take a much clear look at my code just take look at the link
      http://pastebin.com/qcx6xif0


      Delete
    3. sorry for the late reply. There is some release deadline.

      After looking into your code, I noticed some problem when using iterator. It might not be safe to use the same iterator while modifying the container (for your case, the deque). The iterator might be invalidated (see this post http://stackoverflow.com/questions/6438086/iterator-invalidation-rules).

      Besides, I don't recommend you implemented this problem in the way posted in (http://pastebin.com/qcx6xif0). There is better way to do it. You also don't need backtracking or recursive. You can have a loop which repeatedly looking for chances in the string to do the reduction (by scanning the string linearly repeated). If you can't find any chance to reduce, you abort the loop. However, when you do the reduction, you should follow certain rule. It is not that you should always reduce the first pair you observed in the string that can be reduced. For example, if there are two pairs you can reduce, reducing one pair with making you only have "a" in the string (you lost "b" and "c") and reducing the other pair will leave you with both ("c" and "a") in the string, you should try to reduce the second pair first.

      Delete
  5. Hi. I feel that the discussion in step 3 is a bit flawed. Why does the max(num_a,num_b,num_c) always reduce to 1? It may reduce to 2 as well. For example, an arbitrary string may reduce to "bb".

    ReplyDelete
  6. Casinos in New Jersey - MapyRO
    Find the best New Jersey 창원 출장안마 Casinos & play 광명 출장샵 in 성남 출장마사지 one place! 포천 출장마사지 Check out our 제주 출장샵 reviews and find the best casinos in New Jersey. Casinos in New Jersey 10 best casinos in NJ.

    ReplyDelete