Valid Anagram: Character Frequency Comparison | Coding Problems: DSA

Q: How does the sort-and-compare alternative work?

The sortandcompare approach converts both strings to char arrays, sorts them, and compares. If the sorted arrays are equal, the strings are anagrams. This is simpler to write but costs O(n log n) instead of O(n). package com.bank.core; import java.util.Arrays; public class SortCompareAnagram { publi

Definition

Count up for one string and down for the other: equal lengths with all counts zero means valid anagram.

Valid Anagram – two strings of equal length that contain exactly the same characters with identical frequencies.
Balanced count – use an int[26] array; increment for each character of the first string, decrement for each character of the second; all counts must end at zero.
Early exit – return false the moment any count goes negative during the decrement pass.
Length guard – different lengths mean the strings cannot be anagrams; this O(1) check also ensures the single-array invariant.
Complexity – O(n) time and O(1) space for a 26-letter alphabet; O(n) space with a HashMap for Unicode.

The National Bank of India compares two account label strings to decide if one is just a shuffled version of the other, useful for detecting disguised duplicate labels. Imagine a set of counters, one per letter. You add one for each letter in the first label and subtract one for each letter in the second. If every counter lands back at zero, the labels use exactly the same letters.

Understanding the Concepts

What is the Valid Anagram problem?

Given two strings, determine whether one is a rearrangement of the other. Two strings are valid anagrams if they have the same length and contain the same characters with the same frequencies. For example, "listen" and "silent" are valid anagrams.

JAVA

package com.bank.core;

public class ValidAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent")); // true
        System.out.println(isAnagram("hello", "world"));   // false
    }
}

TEXT

true
false

Why is the length check important?

The length check is both a performance optimisation and a correctness guarantee. If two strings have different lengths, they cannot possibly be anagrams. This O(1) check rejects obvious non-anagrams immediately.

More importantly, the length check establishes an invariant: if both strings have the same length and no count goes negative during the decrement pass, then all counts must end at zero. This means you do not need a final loop to verify all counts are zero.

JAVA

package com.bank.core;

public class LengthInvariant {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            System.out.println("Rejected: lengths " + s.length() + " vs " + t.length());
            return false;
        }
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        // No need to check all counts == 0 because lengths are equal
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("abc", "abcd")); // false
        System.out.println(isAnagram("abc", "cba"));  // true
    }
}

TEXT

Rejected: lengths 3 vs 4
false
true

How does the early-negative exit work?

During the decrement pass, if any count drops below zero, the second string has more of that character than the first string provided. This means the strings cannot be anagrams, so you return false immediately without finishing the loop.

JAVA

package com.bank.core;

public class EarlyNegativeExit {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;

        for (int i = 0; i < t.length(); i++) {
            int idx = t.charAt(i) - 'a';
            count[idx]--;
            if (count[idx] < 0) {
                System.out.println("Early exit at index " + i + ": '" + t.charAt(i) + "' excess");
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("aab", "bba")); // false
    }
}

TEXT

Early exit at index 2: 'a' excess
false

How does the sort-and-compare alternative work?

The sort-and-compare approach converts both strings to char arrays, sorts them, and compares. If the sorted arrays are equal, the strings are anagrams. This is simpler to write but costs O(n log n) instead of O(n).

| Feature | Frequency count | Sort-and-compare |
|---|---|---|
| Time | O(n) | O(n log n) |
| Space | O(1) for int[26] | O(n) for sorted copies |
| Early exit | Yes | No |
| Simplicity | Moderate | Very simple |

JAVA

package com.bank.core;

import java.util.Arrays;

public class SortCompareAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("debit", "bited")); // true
    }
}

TEXT

true

How do you handle Unicode or mixed character sets?

When the input is not limited to lowercase ASCII, replace the fixed int[26] array with a HashMap. The logic is identical: increment for the first string, decrement for the second.

JAVA

package com.bank.core;

import java.util.HashMap;
import java.util.Map;

public class UnicodeAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);
        for (char c : t.toCharArray()) {
            int val = count.merge(c, -1, Integer::sum);
            if (val < 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("listen", "silent")); // true
    }
}

TEXT

true

What about case-insensitive comparison?

If the comparison should ignore case, normalise both strings by lowercasing before running the frequency count. If spaces and punctuation should also be ignored, strip non-letter characters first.

JAVA

package com.bank.service;

public class CaseInsensitiveAnagram {
    public static boolean isAnagram(String s, String t) {
        String a = s.toLowerCase().replaceAll("[^a-z]", "");
        String b = t.toLowerCase().replaceAll("[^a-z]", "");
        if (a.length() != b.length()) return false;
        int[] count = new int[26];
        for (char c : a.toCharArray()) count[c - 'a']++;
        for (char c : b.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("Debit Card", "Bad Credit")); // true
    }
}

TEXT

true

What are the edge cases?

Edge cases include empty strings, single characters, strings with all identical characters, and strings that differ in exactly one character.

JAVA

package com.bank.core;

public class AnagramEdgeCases {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (char c : t.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("Empty: " + isAnagram("", ""));       // true
        System.out.println("Single: " + isAnagram("a", "a"));    // true
        System.out.println("All same: " + isAnagram("aaa", "aaa")); // true
        System.out.println("Off by one: " + isAnagram("abc", "abd")); // false
    }
}

TEXT

Empty: true
Single: true
All same: true
Off by one: false

What is the banking use case?

At National Bank of India, Rajesh screens pairs of account labels for shuffled duplicates. A label that is just a rearrangement of an existing one could be an attempt to create a disguised duplicate that evades a uniqueness rule. The system normalises labels by lowercasing and stripping non-letters, then runs the balanced-count check across many pairs. Suspicious matches are flagged for manual review by Priya.

JAVA

package com.bank.service;

public class DuplicateLabelDetector {
    public static boolean isShuffledDuplicate(String existing, String incoming) {
        String a = existing.toLowerCase().replaceAll("[^a-z]", "");
        String b = incoming.toLowerCase().replaceAll("[^a-z]", "");
        if (a.equals(b)) return false; // exact match, not a shuffled duplicate
        if (a.length() != b.length()) return false;
        int[] count = new int[26];
        for (char c : a.toCharArray()) count[c - 'a']++;
        for (char c : b.toCharArray()) {
            if (--count[c - 'a'] < 0) return false;
        }
        return true; // same letters, different arrangement
    }

    public static void main(String[] args) {
        System.out.println(isShuffledDuplicate("Rajesh Account", "Account Rajesh")); // true
        System.out.println(isShuffledDuplicate("Savings", "Savings"));               // false
    }
}

TEXT

true
false

Visual Overview

DIAGRAM

  Valid Anagram: Balanced Count
  ═════════════════════════════

  s = "listen"    t = "silent"

  Step 1: Length check (6 == 6) ✓

  Step 2: Increment for s
  count: [e:1, i:1, l:1, n:1, s:1, t:1]

  Step 3: Decrement for t
  s→0, i→0, l→0, e→0, n→0, t→0
  No count went negative → Valid anagram!

  Early Exit Example:
  s = "aab"    t = "bba"
  count after s: [a:2, b:1]
  decrement t:   b→0, b→-1 → STOP! Not an anagram.

Key Takeaway

Valid Anagram checks whether one string is a rearrangement of another using a balanced frequency count. The approach increments a count per character for the first string and decrements for the second, returning false the instant any count goes negative. The length-first check guarantees that if no count goes negative and both strings have the same length, all counts must end at zero, so no final verification loop is needed.

For a known small alphabet like lowercase ASCII, the int[26] array gives O(n) time and O(1) space. For Unicode or mixed content, switch to a HashMap with the same increment-decrement logic. The sort-and-compare alternative is simpler to write but costs O(n log n).

Normalisation is a decision point: if the comparison should ignore case or spaces, lowercase and strip non-letters before counting. Being explicit about normalisation keeps the behaviour predictable, which matters when the result drives a business rule.

In the banking project at National Bank of India, Rajesh uses this to screen account labels for shuffled duplicates, where a label that is just a rearrangement of an existing one could be a disguised duplicate evading a uniqueness rule. Explaining the length-first guard, the balanced-count invariant, the early-negative exit, and the normalisation choices shows the interviewer that you understand why the technique is correct, not merely that it works.

Remember one sentence: increment counts for one string, decrement for the other, and if all counts end at zero the strings are valid anagrams in O(n) time.

---