Maximal length of a sequence. There is a sequence of letters x and y of length n, represented as an array S[1...n] where each S[i] is either x or y. A segment [i...j] where 1 <= i <= j <= n, is a beautiful segment when the number of x's is equal to the number of y's in the sub-array. The length of the segment is j − i 1, the number of elements in the corresponding sub-array. What is the maximal length of a beautiful segment for this sequence? I have assumed that the maximal length would be n or n-1 given the sequence max length but we do not know how many x's and y's are in the array S.

CodePudding user response：

Walk the sequence left to right, count difference between x and y quantities at every step, and put differences together with positions into dictionary.

If some difference exists, find length as current position - dictionary position and compare with maximal length.

For your example pairs are (bold are the first occurences of key, stored in dictionary)

(0, 0), (1,1), (0,2), (-1,3), (0,4), (-1,5), (-2,6), (-3,7), (-2,8), (-3,9), (-2,10), (-3,11), (-4,12)

We can see some segments of length 4

CodePudding user response：

This is an assessed piece of work for a UK University coursework. If you answer this, you are complicit in plagiarism and just as bad as the original poster.

CodePudding user response：

Nice one you go Warwick? Seems like a coursework doesn't it

CodePudding user response：

STOP Cheating on coursework, why are you doing this