Percentage Of Letter In String - Leetcode Solution

Problem Statement: Given a string s consisting of lowercase letters, you have to compute the percentage of the frequency of each letter that appears in it, rounded to two decimal places.

Example: Input: "aab" Output: ["33.33%","66.67%"] Explanation: 'a' occurs 2 times and 'b' occurs 1 time. The percentage of 'a' is (2/3) * 100 = 66.67% The percentage of 'b' is (1/3) * 100 = 33.33% So the output will be ["33.33%","66.67%"]

Solution: We can solve this problem using efficient string manipulation and array manipulation. Here is how we can solve this:

Step 1: Initialize an array of size 26 (one for each letter of the alphabet) to store the frequency count of each letter.

Step 2: Traverse the input string s and count the frequency of each letter by incrementing the corresponding index in the frequency array.

Step 3: Compute the percentage for each letter by dividing the frequency of each letter by the length of the string and multiplying it by 100. We can format the result to a string with two decimal places using the Python built-in format() function.

Step 4: Return the result array containing the percentage frequency of each letter.

Here's the Python implementation of the above algorithm:

def percentage_of_letters(s: str) -> List[str]: freq = [0] * 26 # Initialize frequency count n = len(s) # Length of the string for c in s: freq[ord(c) - ord('a')] += 1 # Update frequency array res = [] for i in range(26): if freq[i] > 0: pct = (freq[i] / n) * 100 # Calculate percentage frequency res.append(format(pct, '.2f') + '%') # Add to result array return res

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input string s. We iterate over the string once to compute the frequency counts and then iterate over the frequency array once to compute the percentage frequency and store the results.

Space Complexity: The space complexity of this algorithm is O(1) for the frequency array and O(k) for the result array, where k is the number of distinct letters in the input string. Therefore, the total space complexity is O(k).

1