Press "Enter" to skip to content

Posts tagged as “frequency”

花花酱 LeetCode 1370. Increasing Decreasing String

Given a string s. You should re-order the string using the following algorithm:

  1. Pick the smallest character from s and append it to the result.
  2. Pick the smallest character from s which is greater than the last appended character to the result and append it.
  3. Repeat step 2 until you cannot pick more characters.
  4. Pick the largest character from s and append it to the result.
  5. Pick the largest character from s which is smaller than the last appended character to the result and append it.
  6. Repeat step 5 until you cannot pick more characters.
  7. Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:

Input: s = "leetcode"
Output: "cdelotee"

Example 4:

Input: s = "ggggggg"
Output: "ggggggg"

Example 5:

Input: s = "spo"
Output: "ops"

Constraints:

  • 1 <= s.length <= 500
  • s contains only lower-case English letters.

Solution: Counting frequency of each character

Time complexity: O(n * 26)
Space complexity: O(26)

C++

Python3

花花酱 LeetCode 1178. Number of Valid Words for Each Puzzle

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

  • word contains the first letter of puzzle.
  • For each letter in word, that letter is in puzzle.
    For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Constraints:

  • 1 <= words.length <= 10^5
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 10^4
  • puzzles[i].length == 7
  • words[i][j]puzzles[i][j] are English lowercase letters.
  • Each puzzles[i] doesn’t contain repeated characters.

Solution: Subsets

Preprocessing:
Compress each word to a bit map, and compute the frequency of each bit map.
Since there are at most |words| bitmaps while its value ranging from 0 to 2^26, thus it’s better to use a hashtable instead of an array.

Query:
Use the same way to compress a puzzle into a bit map.
Try all subsets (at most 128) of the puzzle (the bit of the first character is be must), and check how many words match each subset.

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzle = “abslute”
bitmap(“aaaa”) = {0}
bitmap(“asas”) = {0, 18}
bitmap(“able”) = {0,1,4,11}
bitmap(“actt”) = {0, 2, 19}
bitmap(“actor”) = {0, 2, 14, 17, 19}
bitmap(“access”) = {0, 2, 4, 18}

bitmap(“abslute”) = {0, 1, 4, 11, 18, 19, 20}

Time complexity: O(sum(len(w_i)) + |puzzles|)
Space complexity: O(|words|)

C++

花花酱 LeetCode 1177. Can Make Palindrome from Substring

Given a string s, we make queries on substrings of s.

For each query queries[i] = [left, right, k], we may rearrange the substring s[left], ..., s[right], and then choose up to k of them to replace with any lowercase English letter. 

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return an array answer[], where answer[i] is the result of the i-th query queries[i].

Note that: Each letter is counted individually for replacement so if for example s[left..right] = "aaa", and k = 2, we can only replace two of the letters.  (Also, note that the initial string s is never modified by any query.)

Example :

Input: s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
Output: [true,false,false,true,true]
Explanation:
queries[0] : substring = "d", is palidrome.
queries[1] : substring = "bc", is not palidrome.
queries[2] : substring = "abcd", is not palidrome after replacing only 1 character.
queries[3] : substring = "abcd", could be changed to "abba" which is palidrome. Also this can be changed to "baab" first rearrange it "bacd" then replace "cd" with "ab".
queries[4] : substring = "abcda", could be changed to "abcba" which is palidrome.

Constraints:

  • 1 <= s.length, queries.length <= 10^5
  • 0 <= queries[i][0] <= queries[i][1] < s.length
  • 0 <= queries[i][2] <= s.length
  • s only contains lowercase English letters.

Solution: Prefix frequency

Compute the prefix frequency of each characters, then we can efficiently compute the frequency of each characters in the substring in O(1) time. Count the number odd frequency characters o, we can convert it to a palindrome if o / 2 <= k.

Time complexity:
preprocessing: O(n)
Query: O(1)
Space complexity: O(n)

C++

花花酱 LeetCode 748. Shortest Completing Word

题目大意: 给你一个由字母和数字组成车牌。另外给你一些单词,让你找一个最短的单词能够覆盖住车牌中的字母(不考虑大小写)。如果有多个解,输出第一个解。

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Example 2:

Note:

  1. licensePlate will be a string with length in range [1, 7].
  2. licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
  3. words will have a length in the range [10, 1000].
  4. Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Idea:

Hashtable

Solution:

C++

Time complexity: 时间复杂度 O(N*26), N is number of words.

Space complexity: 空间复杂度 O(26) = O(1)

 

花花酱 LeetCode 347. Top K Frequent Elements

Problem:

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.



Idea:

 

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

Java

Python

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

C++/array

Java

Python

Related Problems