String problem need help

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

Автор aakarshmadhavan, история, 8 лет назад, По-английски

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?

aakarshmadhavan
8 лет назад
4

Комментарии (4)

Написать комментарий?

SarvagyaAgarwal

8 лет назад, скрыть # |

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.

→ Ответить

SarvagyaAgarwal

8 лет назад, скрыть # ^ |

← Rev. 2 →

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 ;

→ Ответить