aakarshmadhavan's blog

String problem need help
By aakarshmadhavan, history, 8 years ago, In English

The tag says "DP"

I have tried many DP forms

DP[i][j] = true if S[i, j] is a wraparound string`` TLE DP[i] = # of substrign ending at index i``` --> Can't find recurrence because of distinct condition.

Any help?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Seems pretty straightforward. For every character c , store the maximum length of a "good" substring ending at c. Answer would be the sum over all the characters , O(N) time and O(1) space.

→ Reply
  • »
    »
    8 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Something like this should work. 


    int len = p.size() , curr = 0 ;
	vector<int> counts(26,0) ;
	auto next_char = [](char c){
		if(c == 'z') return 'a' ; 
		char x = c + 1 ; 
		return x ;
	};
	for(int i = 0 ; i < len ; ++i) {
		if(i == 0 || p[i] != next_char(p[i &mdash; 1])) {
			curr = 1 ; 
		}
		else ++curr ;
		counts[p[i] &mdash; 'a'] = max(counts[p[i] &mdash; 'a'] , curr) ; 
	}
	cout << accumulate(counts.begin(),counts.end(),0) << endl ;
    → Reply
  • »
    »
    8 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Ah dammit, you finding this "straightforward," is pretty dis-heartening. I'm kind of disappointed I couldn't come up with this.

    How do you come up with solutions like this? Ie, how did you think of this?

    → Reply