WSTRING - Editorial

editorial
, , ,
1

Problem Link:- http://www.codechef.com/JUNE13/problems/WSTRING

Difficulty: Easy

Explanation: First we need to maintain the count for each character b/w two consecutive ‘#’ signs, this we can do by taking vector< vector < int > >. And next we maintain three more arrays to keep track of element with maximum count till 'i’th ‘#’ sign and element having max count b/w ‘i’ and 'i+1’th ‘#’ sign and third array is for maintaining the element with max count from the end of the string till 'i’th ‘#’ sign. Now we start from the first '# sign in the given string and add the values from three arrays, Example: if we are taking 'i’th ‘#’ sign as fist ‘#’ for our WSTRING then we need to add below four value which are:-

  1. count of maximum repeating element till 'i’th ‘#’ sign…which we can get from our first array.
  2. count of maximum repeating element b/w ‘i’ and 'i+1’th ‘#’ sign…retrive from second array.
  3. count of maximum repeating element b/w ‘i+1’ and 'i+2’th ‘#’ sign…retrive from second array.
  4. count of maximum repeating element which are appearing after 'i+2’th ‘#’ sign…retrive from third array.

Add the above four values and move till we reach ‘total _ number _ of _ hash - 3’rd ’ #’ sign and keep updating the maximum length of WSTRING.

Link to my code:-http://www.codechef.com/viewsolution/2221660

2

@nitajay28 don’t put the title as WSTRING - Editorial. This might be confusing. There is already an editorial for this problem. There are people that specialize in doing this. If you have a nicer explanation or solution try and discuss it in the official editorial page.