Problem Link:- http://www.codechef.com/JUNE13/problems/WSTRING
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:-
- count of maximum repeating element till 'i’th ‘#’ sign…which we can get from our first array.
- count of maximum repeating element b/w ‘i’ and 'i+1’th ‘#’ sign…retrive from second array.
- count of maximum repeating element b/w ‘i+1’ and 'i+2’th ‘#’ sign…retrive from second array.
- 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