Valid Anagram - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'gold';

function visMainFunction(inputS, inputT) {
    initClassProperties();
    explanationAndColorSchemaNotifications();
    
    if (inputS.length !== inputT.length) {
        notification(`❌ <b>Not an anagram:</b> The strings have different lengths.`);
        return false;
    }

    startPartialBatch();
    const s = new VisArray(...inputS);
    const t = new VisArray(...inputT);
    notification(`✅ <b>Valid length check:</b> Both strings have ${s.length} characters.<br/>
        <b>Step 1:</b> Build a frequency map for characters of <b>s</b>.`);

    // Build character frequency map for 's'
    const charCounts = new VisMap();

    let sIndex = 0;
    makeVisVariable(sIndex).registerAsIndexPointer(s, CURRENT);

    for (const char of s) {
        charCounts.set(char, (charCounts.get(char) || 0) + 1);
        sIndex += 1;
    }
    endBatch();

    startPartialBatch();
    notification(`📌 <b>Step 2:</b> Consume characters from <b>t</b> against the <code>charCounts</code>.
        <br>• If a character isn’t available, we can <b>immediately</b> conclude “not an anagram”.
        <br>• Otherwise, decrement its count; remove the entry when it reaches <code>0</code>.`);
    let tIndex = 0;
    makeVisVariable(tIndex).registerAsIndexPointer(t, CURRENT);

    // Process string 't' by decrementing from the map
    for (const char of t) {
        if (!charCounts.has(char)) {
            notification(`❌ <b>Mismatch at t[${tIndex}] = "${char}"</b>: no remaining <b>"${char}"</b> available in <code>charCounts</code>.  
                <br>🚫 This means <b>"${inputT}"</b> contains more occurrences of <b>"${char}"</b> than <b>"${inputS}"</b>,  
                so their character frequencies differ — they cannot be anagrams.`);
            return false;
        }

        const newCount = charCounts.get(char) - 1;

        if (newCount === 0) {
            charCounts.delete(char);
        } else {
            charCounts.set(char, newCount);
        }

        tIndex += 1;
    }
    endBatch();

    if (charCounts.size === 0) {
        notification(`✅ <b>Anagram confirmed:</b> All counts balanced out (map is empty) after processing all characters of <code>s</code>.  
            <br>This means each character in <code>s</code> appears the same number of times in <code>t</code>, and vice versa — 
            both strings contain <b>exactly the same multiset of characters</b>.`);
        return true;
    } else {
        notification(`❌ <b>Not an anagram:</b> Unused counts remain in the <code>charCounts</code>, so the strings have different character frequencies.`);
        return false;
    }
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema:</b><br>
        <span class='${CURRENT}' style='background:${CURRENT_COLOR};color:black;'>gold background</span> → 
        Marks the <b>current character</b> being examined in <b>s</b> or <b>t</b> during the frequency map operations.
        <br>This helps visualize which index pointer is active as characters are counted and matched.
    `);
}

function initClassProperties() {
    setClassProperties(CURRENT, {
        backgroundColor: CURRENT_COLOR
    });
}

Approach

To determine whether s and t are anagrams, we compare their character multisets using a single frequency map:

Early exit by length: If s.length !== t.length, they cannot be anagrams → return false.
Build counts from s: Create a hashmap charCounts. For each character ch in s, increment charCounts[ch].
Consume with t: Iterate characters of t:
- If ch is not in charCounts, then t contains more of ch than s → not an anagram → return false.
- Otherwise, decrement charCounts[ch]. If it becomes zero, remove the entry.
Final check: After consuming all of t, if charCounts is empty, then s and t contain exactly the same multiset of characters → return true. Otherwise, return false.

Why this works: By incrementing counts for every character in s and then decrementing for each character in t, the algorithm checks whether the two strings perfectly balance each other’s character frequencies. If a deficit occurs during processing (a missing or overused character) or if any counts remain afterward (charCounts map is not empty), the balance is broken — meaning the strings differ in frequency. If processing completes with no deficits and the charCounts map is empty, it confirms that s and t contain exactly the same multiset of characters, proving they are true anagrams.

Time Complexity

Let n = s.length = t.length. (If their lengths differ, the function exits immediately in O(1) time.)

When lengths are equal, the algorithm runs in O(n) time:

Build counts from s: One pass over s → O(n).
Consume with t: One pass over t → O(n).

Each step performs only constant-time hashmap operations per character, so the total runtime is O(n).

Space Complexity

The frequency map charCounts stores at most one entry per distinct character in s. Since both strings consist of lowercase English letters, there are at most 26 possible keys. Therefore, the auxiliary space is effectively O(1) — constant with respect to input length.

Input-1

Valid Anagram - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity