### Surfer1999's blog

By Surfer1999, 4 months ago,

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

• +4

 » 4 months ago, # |   0
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 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, # ^ |   0 yes right. Substring may or may not contain all the characters.
 » 4 months ago, # | ← Rev. 2 →   -6 nevermind
•  » » 4 months ago, # ^ |   0 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, # ^ |   +8 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, # ^ |   0 Oops really sorry it's wrong, can only applied to problems where substring must consists of all characters.