JavaScript Program Count number of Equal Pairs in a String
In this article, we are going to learn how can we count a number of equal pairs in a string. Counting equal pairs in a string involves finding and counting pairs of consecutive characters that are the same. This task can be useful in various applications, including pattern recognition and data analysis.
Examples:
Input: 'pqr'
Output: 3
Explanation:
3 pairs that are equal are (p, p), (q, q) and (r, r)
Input: 'HelloWorld'
Output: 18
Table of Content
- Naive Approach
- Efficient appraoch
- Using a Map to Count Characters
Naive Approach
The straightforward method involves using two nested loops to iterate through the string, identifying all pairs, and maintaining a count of these pairs.
Example:
// JavaScript program to determine
// the count of equal character pairs
// Function to calculate the
// count of equal character pairs
function fun(str) {
// Length of the input string
let strLength = str.length;
// Variable to store the
// count of equal character pairs
let pairCount = 0;
// Nested loops to compare
// characters for equal pairs
for (let i = 0; i < strLength; i++) {
for (let j = 0; j < strLength; j++) {
// If an equal pair is found
if (str[i] == str[j]) {
pairCount++;
}
}
}
return pairCount;
}
// Driver Code
let str = "w3wiki";
console.log(fun(str));
Output
31
Time Complexity: O(n2), n is the length of input string
Space Complexity: O(1)
Efficient appraoch
- In this approach, We must efficiently determine the count of distinct pairs of characters in linear time.
- Notably, pairs like (x, y) and (y, x) are treated as distinct.
- To accomplish this, we employ a hash table to record the occurrences of each character. If a character appears twice, it corresponds to 4 pairs: (i, i), (j, j), (i, j), and (j, i).
- By utilizing a hashing mechanism, we keep track of the frequency of each character, and for each character, the count of pairs will be the square of its frequency.
- The hash table will have a length of 256 since there are 256 distinct characters.
Example: This example shows the use of the above-explined approach.
// JavaScript program to calculate the
// count of pairs
const MAX = 256
// Function to calculate the count
// of identical pairs
function fun(str) {
// Hash table to store
// character counts
let charCount = new Array(MAX).fill(0)
// Iterate through the string and tally
// the occurrences of each character
for (let i = 0; i < str.length; i++)
charCount[str.charCodeAt(i) - 97] += 1
// Variable to hold the final count of pairs
let pairCount = 0
// Iterate through the characters and check
// for occurrences
for (let i = 0; i < MAX; i++)
pairCount += charCount[i] * charCount[i]
return pairCount
}
// Driver code
let str = "pqr"
console.log(fun(str))
Output
3
Time Complexity: O(n), n is the length of input string
Space Complexity: O(1)
Using a Map to Count Characters
Using a Map, the approach counts characters by iterating over the string. For each character, it updates the count in the Map. Finally, it calculates the count of equal pairs by summing up the counts multiplied by one less than the count.
Example: This function counts the number of equal adjacent pairs in a string by using a Map to track the count of each character.
function countEqualPairs(str) {
let count = 0;
let charCount = new Map();
for (let char of str) {
if (charCount.has(char)) {
count += charCount.get(char);
charCount.set(char, charCount.get(char) + 1);
} else {
charCount.set(char, 1);
}
}
return count;
}
console.log(countEqualPairs("abccba")); // 5
Output
3
Contact Us