Surfer1999's blog

By Surfer1999, 22 months ago, In English

Given a string s, return the length of longest substring such that every character in the substring has equal number of occurance.

I tried to find solution better that O(n*n) but didn't succeed. Can it be solved in better than O(n*n) ? source of the problem: https://leetcode.com/discuss/interview-question/2116387/google-oa/1424270

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    The statement is a bit different. In the problem on the blog, the substring doesn't have to contain all the characters in the string. For example, in the string abcaad, the substring abc is good in one version but not in the other.

»
22 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

nevermind

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    for example: take "deefffaabb", here answer is 6 i.e substring "ffaabb". According to your solution f[9]=f[3]. But f[1]={d=1,e=2,f=1} and subtracting the minimum gives {d=0,e=1,f=0}. For f[9]={d=1,e=2,f=3,a=2,b=2}, subtracting minimum gives {d=0,e=1,f=2,a=1,b=1}. Here value of character 'f' differs.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops really sorry it's wrong, can only applied to problems where substring must consists of all characters.