// Example: S = "aabbbcdddcc", K = 3
i,j // i, j start at 1
S = [ a, A, b, b, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0 ] // S[i] == S[i-1], no change
->i,j // i, j move up 1
S = [ a, a, B, b, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ] // S[i] != S[i-1], st.push(i)
->i,j // i, j move up 1
S = [ a, a, b, B, b, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ] // S[i] == S[i-1], no change
->i,j // i, j move up 1
S = [ a, a, b, b, B, c, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ] // S[i] == S[i-1], no change
i<-------j // i moves back because...
S = [ a, a, B--B--B, c, d, d, d, c, c ] // ...3 b's found, so...
st = [ 0 ] // ...i = st.pop() - 1
->i ->j // i, j move up 1
S = [ a, a, C<-------C, d, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2 ] // new letter, st.push(i)
->i ->j // i, j move up 1
S = [ a, a, c, D<-------D, d, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ] // new letter, st.push(i)
->i ->j // i, j move up 1
S = [ a, a, c, d, D<-------D, d, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ] // S[i] == S[i-1], no change
->i ->j // i, j move up 1
S = [ a, a, c, d, d, D<-------D, c, c ] // S[j] overwrites S[i]
st = [ 0, 2, 3 ] // S[i] == S[i-1], no change
i<-------- j // i moves back because...
S = [ a, a, c, D--D--D, , , , c, c ] // ...3 d's found, so...
st = [ 0, 2 ] // ...i = st.pop() - 1
->i ->j // i, j move up 1
S = [ a, a, c, C<----------------C, c ] // S[j] overwrites S[i]
st = [ 0, 2 ] // S[i] == S[i-1], no change
->i ->j // i, j move up 1
S = [ a, a, c, c, C<----------------C ] // S[j] overwrites S[i]
st = [ 0, 2 ] // S[i] == S[i-1], no change
i<-------- j // i moves back because...
S = [ a, a, C--C--C, , , , , , ] // ...3 c's found, so...
st = [ 0 ] // ...i = st.pop() - 1
S = [ a, a ] // only keep S up to i
= "aa" // then join to a string
Not able to imagine stack approach in java
very difficult to do dry run
Here's an example, hopefully it helps!
wow thanks :)
I got it