Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Strings

Valid Anagram

Easy · Strings · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Two strings are anagrams if one can be rearranged into the other. Print YES or NO.

Input

Two lines: strings s and t (lowercase letters).

Output

YES or NO.

Constraints

Count letters with an array of size 26.

Example 1

Input

anagram
nagaram

Output

YES

Example 2

Input

rat
car

Output

NO

Hints

  1. Anagrams contain exactly the same letters the same number of times.
  2. Count letters with an int array of size 26: +1 for each letter of s, −1 for each letter of t.

Approach

If the lengths differ, the answer is NO. Otherwise count: add 1 for each letter of s and subtract 1 for each letter of t in a 26-slot array. The strings are anagrams if every slot ends at 0. Sorting both strings and comparing also works, in O(n log n).

Complexity: O(n) time · O(1) extra space (26 counters)

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;
    for (char c : t) cnt[c - 'a']--;
    bool ok = s.size() == t.size();
    for (int i = 0; i < 26; i++)
        if (cnt[i] != 0) ok = false;
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

from collections import Counter

s = input().strip()
t = input().strip()
print("YES" if Counter(s) == Counter(t) else "NO")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(), t = sc.next();
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        for (char c : t.toCharArray()) cnt[c - 'a']--;
        boolean ok = s.length() == t.length();
        for (int x : cnt)
            if (x != 0) ok = false;
        System.out.println(ok ? "YES" : "NO");
    }
}

Solve Valid Anagram online · All practice problems