Surfer1999's blog

By Surfer1999, 4 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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 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.

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

      yes right. Substring may or may not contain all the characters.

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

nevermind

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

    I don't think it would work. It seems your solution is similar to told by timg8710. Can you take an example ?

  • »
    »
    4 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.

    • »
      »
      »
      4 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.