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

Stuck on a problem
Автор -VIBE, история, 15 месяцев назад, По-английски

Can anyone help me with my last submission. Approach-> 1)Lets take any two strings(say s1 and s2). 2)Now create a string ans from s1 and s2 by taking first character from s1 and then s2 and then repeat. At last we have size of our string ans=4*n. 3)Now i will pair the consecutive same number in the ans string. 4)Now if size of ans is less than or equal to 3*n then it will be my ans otherwise i will create my ans string from s2 and s3,then check for it and lastly check for s1 and s3. Note-> A number can only be paired once. Thanks in advance

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

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

provide question link

→ Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Actually, you are pairing them wrong.

Let's take these two strings:

000111

111000

(here n=3)

By your algorithm, the merged string comes out to be '010101101010' and then you merge '11'. The string becomes '01010101010'. The length is 11 which is greater than 3*n=9, so you say that this merging is not possible and move forwards to compare s2 and s3.

Whereas, the string '000111000' has length 9 and contains both strings as it's subsequence.

→ Ответить
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ya i got the mistake , but could there be any third string along with these two such that ans will not exist for three of them. Coz i guess my ans will come for the third string

    → Ответить
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Below is an counter-example with all 3 strings. All the 6 merging results exceeds maximal length 12: 11111000 00000000 00101111

        11111000 00000000 -> 1010101010000
  11111000 00101111 -> 10101101010101
  00000000 11111000 -> 0101010101000
  00000000 00101111 -> 0001001010101
  00101111 11111000 -> 0101101101010
  00101111 00000000 -> 0010010101010
      → Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my stepsister is stuck in the washing machine too

→ Ответить