lastlife's blog

Doubt in yesterday's C question
By lastlife, history, 13 months ago, In English

Guys can someone help me out as to why this logic fails

342334437

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Here's what I found wrong with this code as someone who has solved this problem:

1: Initialization of mini = INT_MAX and checking of "if(mini != n)". This should be "if(mini != INT_MAX)" since mini is almost never equal to n, resulting in printing INT_MAX or something else instead of the intended -1 when you don't find a valid substring.

2: Code runs in O(n^2) with worst-case scenarios because you track all of acount and bcount in a set and bruteforce j values, and you could do it in O(n) with prefix sums and a hash-map storing earliest prefix index.

Hope this helps!

→ Reply
  • »
    »
    13 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Won't mini always become n in the end because a possible soln is to always remove the entire elements of the string

    Also I did figure out where my code was going wrong. I was checking and updating mini only when c[x]-c[y]>=delta but right answer can exist for any c[x] and c[y] and you're right it's an N^2 soln but like I just wanted to understand that for which input my logic giving wrong answer. Thanks for helping out man!

    → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      The reason mini won’t always become n in the end is because the problem explicitly asks to print -1 when the only way to equalize counts is to remove the entire string (“If it is necessary to remove all letters from the string s (i.e., make it empty), report this”). So if your solution treats a removal of length n as valid instead of printing -1, it would be considered incorrect according to the problem statement.

      → Reply
      • »
        »
        »
        »
        13 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it 
        if(mini!=n){
    cout<<mini<<'\n';
}
else{
    cout<<"-1\n";
}

        isn't this doing that then, and also man I feel super dumb atp you're solving 3000+ rated questions and I'm asking beginner doubts btw I did solve this question now using the hash map and prefix approach thanks again <3.

        → Reply
        • »
          »
          »
          »
          »
          13 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          The problem with if(mini != n) check is that it only works if the only invalid solution is removing the entire string, but in the original code, mini could never be set to n in most cases, like if no valid substring existed. As a result, you'd either skip printing -1, or print a wrong value such as INT_MAX, which is why the correct check should be if(mini != INT_MAX && mini != n).

          Glad I could help you solve it :)

          → Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Sorry to say, but the code looks a bit messy (for me -_- ). From what I understand, you’re comparing the delta of prefix and suffix, and I think your logic and mine are actually the same — just implemented differently. You can follow this code : 342354714, Ig.

→ Reply