Leetcode 242. Valid Anagram

Accepted Code

Problem Statement

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Test Cases

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 * 104
  • s and t consist of lowercase English letters.

Approach

Two words are said to be anagrams if they have the same amount of characters. It is not at all necessary that two words have to be equal, but they must have the same character with equal frequency.

In order to check whether two words are anagrams, we can sort the two strings and check whether one word equal to the other one. Actually, we can do better instead of applying sorting to the strings. We are only concerned about the frequency and the characters. So we can have a count array of size say 26 for this problem and increment the counter array while traversing through one of the strings. Then traverse through the next string and this time just decrement the counter array for each of the characters. If the two strings are anagrams, then the final values inside the counter array will be 0, otherwise not an anagram.

Algorithm

  1. Check whether two strings have the same length as a base case.
  2. Initialize an array of size 26 which tracks the frequency of each character.
  3. Traverse through the first string and increment the counter for each character.
  4. Traverse through the second string and decrement the counter for each character.
  5. Check whether any of the values inside the counter array is not zero. If not zero, then no anagram.
  6. Finally, return the true if all the values are zero inside the counter array.

Time and Space Complexity

We are traversing through the two strings which must be of the same length + counter array of size 26. So our time complexity will be O(26 + n + n) where n = length of the strings.

We are making use of an array of sizes 26. So our space complexity will be O(26).

Code

Java Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohith Vazhathody

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.