Блог пользователя sam_2912

Problem: Nice Strings.
Автор sam_2912, история, 22 месяца назад, По-английски

A string of length K is called a nice if the frequency of one of its characters is greater than or equal to floor(K/2). You are given a string s of length N, find the length of longest nice substring.

Input format

  • First line: T number of test cases.

  • For each test case first line contains N, i.e., length of string s and next line contains the string s itself containing only lower case English letters.

Output format

  • For each test case output the length of longest nice substring.

Sample Input

  • 1
  • 5
  • abcde

Sample Output

  • 3

Constraints

  • T <= 10
  • N <= 10^5
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
22 месяца назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Since I don't have the source and complete test cases of this problem I want to discuss my approach and seek for any better approach.

My approach For every character c from 'a' to 'z', I will assume that c gives the longest nice substring. I can thus convert this problem into finding the longest positive subarray from the array arr[] such that arr[i] == 1 if s[i] == c else arr[i] == -1. Given that an O(N) approach exists for this we are able to solve the problem in essentially O(26*N) time. Is this a right approach given the constraints? Is there a better approach had the character set been much larger than 26?

→ Ответить
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Binary search + sliding window

→ Ответить
»
22 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

We can solve it using binary search.

Binary search on value of longest substring and make a corresponding check condition.

For a mid value simply iterate over all mid sized subarrays of string and for each subarray find the max frequency of any character in it and check if it has value >= floor(mid/2)

For finding character with maximum frequency simply u can maintain a set of pairs or there are a lot of other ways too to do this.

Time Complexity: N*(log n*log n)

→ Ответить
  • »
    »
    22 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    This property is not monotonic/binary searchable. For example, there are no nice substrings of length 6 in "aabcdeaa", but there is one with length 8.

    → Ответить