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