_humblefool_'s blog

How to solve this problem in Linear time or less than O(n^2) ?
By _humblefool_, history, 2 years ago, In English

Problem link I did not find any better solution in the discuss section of leetcode that's why posting here.

  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
2 years ago, # |
  Vote: I like it -30 Vote: I do not like it

It is very disappointed to see that useless blog gets upvotes and a lot of people comment on those blogs but I even did not got any answer of my genuine problem. I was thinking that there are so many genius coders that will answer my problem. Shame on you CodeForces community.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sometimes the comunity is obviously being biased, but let not just focus on the vote since it is not that important, compared to the important of current knowledge — which can be easily comprehend through the color.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the need of it? You can write simple O(n^3) solution.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even if sometimes gray coders make stupid questions, we should not just be so mean to those new leaner about everything. Sometimes they just curious to ask to become better. Chill :/

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think I can solve it

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am curious if we can really solve in linear tho hmmmm

    → Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

By quick thinking, $$$O(n^2 + alphabet)$$$ is possible if you iterating each letter and increase its frequency while maintaining the maximum and the minimum

int n = s.size();
long long res = 0;
for (int i = 0; i < n; ++i)
{
    for (int j = i; j < n; ++j)
    {
        ++cnt[s[j]];
        update(max); <-- you can just maximize(max, ++cnt[s[j]]); at the beginning
        update(min); <-- this can be a bit tricky to get O(1), but O(log alphabet) coding is simpler
        res += max - min;
    }

    for (int j = i; j < n; ++j)
        --cnt[s[j]];
}
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it is easy to do that. But how can we solve it less than n^2?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am pretty sure with this kind of problem we can do $$$O(n \sqrt{n})$$$ or faster, but it seems trickier than I thought it would

      → Reply