Algorithm Patterns 101: Character Mapping

You will often be ask questions in interview settings that involve finding patterns within strings.

In order to correctly track and correlate where characters exist, we need to use something called a character map.

In this scenario, I am attempting to turn my name “Teddy” into a char map. While called a “map” (which can be confused with a traditional Map data structure), it is actually more less an object.

Common character map scenarios include:

• Write a function that, when given a string, returns the character that is most commonly used
• How many vowels are in a sting
• Anagram testing

Step-by-Step

1. Initialize an empty object to hold char map
2. Create a variable to hold the max value
3. Create a variable to point to the most common character

function mostCommonChar(str) {
    let charMap = {}
    let max = 0
    let maxChar = ''
}

Now, iterate through the string and create some key/value pairs:

function mostCommonChar(str) {
    let charMap = {}
    let max = 0
    let maxChar = ''

    for (let char of str) {
        if(!charMap[char] > max) {
            charMap[char] = 1
        } else {
            charMap[char]++
        }
    }
}

Within the for loop logic, we check to see if charMap already contains a key for each char. Attempting to access a key that doesn’t exist will return null, so we implement fail first logic to handle edge cases.

The char mapper is looking good, but now we need to actually implement the logic to find the most common character.

• First, we will use a for in loop to iterate through the character map.

function mostCommonChar(str) {
    let charMap = {}
    let max = 0
    let maxChar = ''

    for (let char of str) {
        if(!charMap[char]) {
            charMap[char] = 1
        } else {
            charMap[char]++
        }
    }
    for(let char in charMap) {      //iterate over the object we created
        if(charMap[char] > max) {     //if the value is greater than max
            max = charMap[char]     //update new max value
            maxChar = char          //dry the max char
        }
    }
    return maxChar
}

Anagrams

Anagrams are words formed by rearranging the letters of another, such as:

• Cinema
• Below
• Study
• Night
• Cat

Step-By-Step Anagrams

function anagrams(stringA, stringB) {
    // create two char maps for each string set
    const aCharMap = buildCharMap(stringA);
    const bCharMap = buildCharMap(stringB);

    //Turn our object into an array of keys and check the lengths for equality
    if(Object.keys(aCharMap).length !== Object.keys(bCharMap).length) {
        return false;
    } 

    //Iterate over values in object and check values for equality.
    for(let char in aCharMap) {
        if(aCharMap[char] !== bCharMap[char]) {
            return false;
        }
    }

    return true;
}

function buildCharMap(string) {
    //Initalize char map object to store a new version of our array.
    const charMap = {};

    //Create a for loop. In this case, we use for with a regex that filters out all non characters + lowercases
    for(let char of string.replace(/[^\w]/g, '').toLowerCase()) {
        //Access char map object at iteration value. If no value exists add 1, else increment.
        charMap[char] = charMap[char] + 1 || 1;
    }
    // return map
    return charMap;
}

• First, we build a char map that

Char maps are great for comparing, tracking, and performing computations on strings. Next time you have an interview where strings are being analyzed, be sure to use this algorithm technique!

Conclusion