Блог пользователя aakarshmadhavan

String problem need help
Автор aakarshmadhavan, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 ;
    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить