Valid Anagrams - Leet Code Solution

September 10, 2020

Problem Statement

Given two strings s and t , write a function to determine if t is an anagram of s.

Example

``````Input: s = "anagram", t = "nagaram"
Output: true

Input: s = "rat", t = "car"
Output: false``````

Note: You may assume the string contains only lowercase alphabets.

What is Anagram

First try to understand what an Anagram is. Its NOT about checking order of characters in a string.

• Each character in both strings has equal number of occurrence.

Solution - 1

A simple solution can be to sort the strings first, then compare.

Code

``````public boolean isAnagram_sort(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] s1 = s.toCharArray();
char[] s2 = t.toCharArray();
Arrays.sort(s1);
Arrays.sort(s2);

return Arrays.equals(s1, s2);
}``````

Complexity

It is equal to complexity taken by sorting.
Its `O(nlogn)`

Solution using counting number of characters - HashMap

Another simple solution is that we can use a `HashMap<Character, Integer>`.

• In one pass of first array, we can populate HashMap, which will have count of each character
• In iteration of second array, we can simply decrement count of found characters
• At any time, if the count becomes zero before we decrementing it. Which means, character count do not match.

Code

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

Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<s.length(); i++) {
int count = map.getOrDefault(s.charAt(i), 0);
count ++;

map.put(s.charAt(i), count);
}

for (int i=0; i<t.length(); i++) {
int count = map.getOrDefault(t.charAt(i), 0);
if (count == 0) {
return false;
}

count --;
map.put(t.charAt(i), count);
}

return true;
}``````

Complexity

Its `O(n)`

Solution by using array

Since we know that there are only `lowercase characters`. We know the unique number of characters will be `26`.

• We can take an `Integer array` of `count 26`
• We can assume that first index corresponds to `a`, second to `b` and so on.
• In first pass of an array, we can increment count according to location mentioned above
• While iterating second array, we can simply start decrementing count.
• And, at any point if we found the count to be negative. We return false.

Code

``````public boolean isAnagram_array(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'] ++;
}

for (int i=0; i<t.length(); i++) {
if (count[t.charAt(i) - 'a'] <= 0) {
return false;
}
count[t.charAt(i) - 'a'] --;
}

return true;
}``````

Note that `t.charAt(i) - 'a'` is just to manipulate our indexes.

Complexity

Its `O(n)`

Similar Posts

Valid Palindrome - Leet Code Solution

Problem Statement Given a string, determine if it is a palindrome, considering…

What FAANG companies expect in their interview from candidates

Its every software engineer’s dream to work with the big FAANG companies…

Remove Duplicates from Sorted Array - Leet Code Solution

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

Convert Roman to Integer number - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

Min Priority Queue Implementation with Heap Data structure

Min Priority Queue is a data structure which manage a list of keys(values). And…

Latest Posts

Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…