Problem Statement
Count the frequency of each character in a string and return it as an object.
Example Inputs
- Input:
"hello"
- Output:
{ h: 1, e: 1, l: 2, o: 1 }
- Input:
"character"
- Output:
{ c: 2, h: 1, a: 2, r: 2, t: 1, e: 1 }
- Input:
"frequency"
- Output:
{ f: 1, r: 1, e: 2, q: 1, u: 1, n: 1, c: 1, y: 1 }
- Input:
"JavaScript"
- Output:
{ J: 1, a: 2, v: 1, S: 1, c: 1, r: 1, i: 1, p: 1, t: 1 }
JavaScript Method - Using Only String Methods
Approach
To count the frequency of each character, we can use a loop to iterate over each character in the string and an object to store character counts.
Steps
- Initialize an empty object
frequency.
- Loop through each character in the string.
- For each character, if it already exists as a key in
frequency, increment its value.
- If it doesn’t exist, set its value to 1.
- Return the
frequency object.
Time & Space Complexity
- Time Complexity: O(n), where n is the length of the string, as we process each character once.
- Space Complexity: O(k), where k is the number of unique characters, since each unique character is stored in the object.
Code Snippet
Dry Run
Example input: "hello"
- Initialize:
frequency = {}
- Loop through
"hello":
h → frequency = { h: 1 }e → frequency = { h: 1, e: 1 }l → frequency = { h: 1, e: 1, l: 1 }l → frequency = { h: 1, e: 1, l: 2 }o → frequency = { h: 1, e: 1, l: 2, o: 1 }
- Final output:
{ h: 1, e: 1, l: 2, o: 1 }
Alternative Approach - Using Map Data Structure
Approach
Using a Map data structure provides an efficient way to store character frequencies, especially with case sensitivity. We can loop through each character and update its count in the Map.
Steps
- Initialize an empty
Map object.
- Loop through each character in the string.
- If the character already exists in the
Map, increment its value.
- If it doesn’t exist, set its value to 1.
- Convert the
Map to an object for a consistent output format.
Time & Space Complexity
- Time Complexity: O(n), as each character is processed once.
- Space Complexity: O(k), where k is the number of unique characters.
Code Snippet
Dry Run
Example input: "hello"
- Initialize:
frequencyMap = Map {}
- Loop through
"hello":
h → Map { h => 1 }e → Map { h => 1, e => 1 }l → Map { h => 1, e => 1, l => 1 }l → Map { h => 1, e => 1, l => 2 }o → Map { h => 1, e => 1, l => 2, o => 1 }
- Convert
Map to object: { h: 1, e: 1, l: 2, o: 1 }
Complexity Analysis
JavaScript Method (Using String Methods)
- Time Complexity: O(n)
- Space Complexity: O(k)
Alternative Approach (Using Map)
- Time Complexity: O(n)
- Space Complexity: O(k)
Conclusion
Counting character frequency in a string can be achieved using either an object or a Map data structure. Both methods provide similar time complexity, but using Map may offer benefits in larger applications, particularly for complex data manipulations.