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

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

Given a binary string find the length of longest subsequence (NOT substring) which matches the regex 0*1*0*1*

Here * means the preceding character can occur zero or more times.

Eg input — 0101000, output — 6 (011000)
Eg input — 0101 output — 4 (0101) Constraint — Length of string = N < 10^5

My approach:

The valid string can be one of seven types:

  • 0 only zeros
  • 1 only ones
  • 01 some zeroes followed by some ones
  • 10 some ones followed by some zeros
  • 010 some zeros then some ones then some zeros
  • 101 some ones then some zeros then some ones
  • 0101 some zeros then some ones then some zeros and then some ones.

Now my dp[i][j] is the maximum length subsequence from 0 to i which forms the valid string of jth form where 0<=j<7.

My code : link

Is this approach correct and if not can someone provide a test case where this might fail. Thankyou.

P.S. This question was from a hiring test that is over now and I don't have the link to the problem.

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

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

Auto comment: topic has been updated by John_Cena (previous revision, new revision, compare).

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

Anyone out there help

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

It's hard to check your DP transitions, but your states seems correct according to your formulation.

I have written my own DP — you can use a generator to stress-test the two solutions: Link

I tested it on 2-3 random small cases — the outputs matched.