Percentage of Letter in String
EasyPrompt
Given a string s and a character letter, return the percentage of characters in s that equal letter rounded down to the nearest whole percent.
Example 1:
Input: s = "foobar", letter = "o"
Output: 33
Explanation:
The percentage of characters in s that equal the letter 'o' is 2 / 6 * 100% = 33% when rounded down, so we return 33.Example 2:
Input: s = "jjjj", letter = "k"
Output: 0
Explanation:
The percentage of characters in s that equal the letter 'k' is 0%, so we return 0.
Constraints:
1 <= s.length <= 100sconsists of lowercase English letters.letteris a lowercase English letter.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach calculates the count of the target letter by leveraging string manipulation. It determines the number of occurrences by comparing the original string's length with the length of a new string created by removing all instances of the target letter.
Algorithm
- Get the original length of the string
s. - Create a new string by removing all occurrences of
letterfroms. This can be done usings.replace(String.valueOf(letter), ""). - The count of
letteris the difference between the original length and the new string's length. - Calculate the percentage using integer division:
(count * 100) / original_length. This automatically handles the rounding down.
Walkthrough
The core idea is to find the difference in length before and after removing the specified letter from the string s. The number of characters removed is equal to the number of occurrences of that letter.
- Store the original length of the string
s. - Create a new string by replacing all occurrences of
letterwith an empty string. - Calculate the count of
letterby subtracting the new string's length from the original length. - Calculate the percentage using the formula:
(count * 100) / original_length. - Since we are performing integer division, the result is automatically floored (rounded down), which matches the problem's requirement.
class Solution { public int percentageLetter(String s, char letter) { int originalLength = s.length(); // Create a new string without the target letter String newString = s.replace(String.valueOf(letter), ""); int newLength = newString.length(); // The count is the difference in lengths int count = originalLength - newLength; // Calculate percentage using integer division for flooring return (count * 100) / originalLength; }}Complexity
Time
O(N), where N is the length of the string `s`. The `replace()` method needs to scan the entire string to find and replace characters, which takes linear time.
Space
O(N), where N is the length of the string `s`. A new string is created by the `replace()` method. In the worst case (if the letter is not found), the new string has the same length as the original, requiring O(N) space.
Trade-offs
Pros
Can be written concisely.
Leverages built-in string functions, which can be expressive.
Cons
Less efficient in terms of space due to the creation of a new string object.
The
replaceoperation might have a higher constant time factor than a simple loop.
This is the most direct and efficient approach. It involves a single pass through the string to count the occurrences of the target letter. This avoids the overhead of creating new strings and minimizes memory usage.
Algorithm
- Initialize a counter variable,
count, to zero. - Iterate through each character of the input string
sfrom the first to the last character. - For each character, check if it is equal to the target
letter. - If it matches, increment the
count. - After the loop finishes, the
countwill hold the total number of occurrences. - Calculate the percentage using integer division:
(count * 100) / s.length(). This naturally rounds the result down.
Walkthrough
We iterate through the string character by character, keeping a running count of how many times we encounter the specified letter.
- Initialize a counter variable,
count, to zero. - Iterate through each character of the input string
s. - For each character, check if it is equal to the target
letter. - If it matches, increment the
count. - After the loop finishes, the
countwill hold the total number of occurrences. - Calculate the percentage:
(count * 100) / s.length(). The integer division naturally rounds the result down.
Here is the implementation using a standard for-loop, which is the most space-efficient:
class Solution { public int percentageLetter(String s, char letter) { int count = 0; int n = s.length(); for (int i = 0; i < n; i++) { if (s.charAt(i) == letter) { count++; } } return (count * 100) / n; }}An alternative implementation can use an enhanced for-loop, which is slightly more concise but uses more space by creating a temporary character array:
class Solution { public int percentageLetter(String s, char letter) { int count = 0; for (char c : s.toCharArray()) { if (c == letter) { count++; } } return (count * 100) / s.length(); }}Complexity
Time
O(N), where N is the length of the string `s`. We need to visit each character of the string exactly once.
Space
O(1). We only use a constant amount of extra space for variables like the counter and loop index. The space used does not depend on the size of the input string. Note that using an enhanced for-loop with `s.toCharArray()` would create a temporary character array, resulting in O(N) space complexity, but a standard index-based loop achieves O(1) space.
Trade-offs
Pros
Optimal time complexity as it requires only one pass.
Optimal space complexity (O(1)) when using an index-based loop.
Easy to understand, implement, and debug.
Cons
Slightly more verbose than a one-liner using built-in functions.
Solutions
Solution
class Solution {public int percentageLetter(String s, char letter) { int cnt = 0; for (char c : s.toCharArray()) { if (c == letter) { ++cnt; } } return cnt * 100 / s.length(); }}class Solution {public: int percentageLetter(string s, char letter) { int cnt = 0; for (char &c : s) cnt += c == letter; return cnt * 100 / s.size(); }};class Solution: def percentageLetter( self, s: str, letter: str) -> int: return s . count(letter) * 100 // len(s)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.