Problem: Leet Code 242 - Valid Anagram

QUESTION:

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:

Input: s = "anagram", t = "nagaram"

Output: true

Example 2:

Input: s = "rat", t = "car"

Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 10<sup>4</sup>

  • s and t consist of lowercase English letters.


💭Analyzing question:

  1. Anagram means a new string for instance ‘t’ can be formed from an existence string ‘s’ by interchanging the letters of the existing string to form a sensible word.

  2. The question is to check for valid anagram, out of given inputs ‘s’ and ‘t’, we should state whether ‘t’ is an anagram of ‘s’.


💡Approach:

  • My approach was to use two ArrayList, a collection to store characters of string s and t in it.

  • Then using built-in to sort the ArrayList and check if both are equal, this one takes two operations to be done at a time, both sorting and comparison

  • That’s why we look forward for an approach that could tell whether the string ‘t’ is anagram of string ‘s’ by keeping track of the occurrences of the occurred character in the string ‘s’, and checking it with the string ‘t’, whether same or not, based on that we return true or false.

  • So, we use array named count to store the occurrences of the characters in the string ‘s’ and then finally decrement that by checking the occurrences for string ‘t’.

  • Finally, we check whether all values of count array are zero or not, if zero we return true, else we return false, as ‘t’ may not be anagram, as might miss any character.


💻My Java Code:

Brute force Approach

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;

        List<Character> list1 = new ArrayList<>();
        List<Character> list2 = new ArrayList<>();

        for (char c : s.toCharArray()) list1.add(c);
        for (char c : t.toCharArray()) list2.add(c);

        Collections.sort(list1);
        Collections.sort(list2);
        return list1.equals(list2))
     }
}

Optimal Approach

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

🖥️Output:


⏱️Efficiency of my Approaches:

Brute force Approach

  • Time Complexity: O (N log N)

  • Space complexity: O(N)

Optimal Approach

  • Time Complexity: O(N)

  • Space complexity: O(1)


🧠My Learnings:

  1. Array List and its built-in functions

  2. ASCII value to keep track of occurrences of character in String


Tags:

#Java #Leetcode #ProblemSolving #DSA

0
Subscribe to my newsletter

Read articles from ARCHANA GURUSAMY directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

ARCHANA GURUSAMY
ARCHANA GURUSAMY

👩‍💻 I'm Archana Gurusamy, a passionate 3rd-year B.Tech IT student on a mission to grow as a developer.I'm currently deep-diving into Data Structures & Algorithms using Java, while also exploring web development and real-world projects. I love solving coding challenges, building meaningful applications, and documenting my learning journey through technical blogs. I believe in learning in public — sharing my logic, code, and even my rough ideas as I grow. I'm actively working on building a strong IT profile while preparing for real world challenges.