aakarshmadhavan's blog

String problem need help
By aakarshmadhavan, history, 7 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

»
7 years ago, # |
  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
  • »
    »
    7 years ago, # ^ |
    ← 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
  • »
    »
    7 years ago, # ^ |
      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
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I dont know how to answer this. This just comes from practice i guess.

      → Reply