Twenty Percent Knowledge: anagram

Saturday, June 25, 2016

Sherlock and Anagrams

Given a string

, find the number of "unordered anagrammatic pairs" of substrings.
Input Format
First line contains

, the number of testcases. Each testcase consists of string

in one line.
Constraints

String

contains only the lowercase letters of the English alphabet.
Output Format
For each testcase, print the required answer in one line.
Sample Input#00

2
abba
abcd

Sample Output#00

4
0

Sample Input#01

5
ifailuhkqq
hucpoltgty
ovarjsnrbf
pvmupwjjjf
iwwhrlkpek

Sample Output#01

Explanation
Sample00
Let's say

denotes the substring

.
testcase 1:
For S=abba, anagrammatic pairs are:

and

.
testcase 2:
No anagrammatic pairs.
Sample01
Left as an exercise to you.

Analysis

this seems complex, I have no optimized way to work it out. brute force way is working and basic idea is as follow:

1. categorize the substrings into categories according to their length, because anagram is between strings with same length(same length, same number of characters). single character is also a substring.

2. within each category, calculate the number of anagram pairs

3. sum numbers from all categories.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] ss = new String[n];
        for(int i=0;i<n;i++){
            checkAnagramPairs(in.next());
        }
        
    }
    /**
    two steps:
    1.categorize the substrings, same length strings are put together
    2. figure out num of pairs in each category
    3. sum 2
    */
    private static void checkAnagramPairs(String s){
        if(s==null||s.length()==1)System.out.println(0);
        Map<Integer,List<String>> stats = new HashMap<Integer,List<String>>();
        for(int i=0;i<s.length();i++){
            for(int j=i+1;j<=s.length();j++){
                if(stats.get(j-i)==null){
                    List<String> l = new ArrayList<String>();
                    l.add(s.substring(i,j));
                    stats.put(j-i,l);
                }else{
                    stats.get(j-i).add(s.substring(i,j));
                }
            }
        }
        int ttl = 0;
        for(Map.Entry<Integer,List<String>> e:stats.entrySet()){
            ttl+=getNumOfAnagramPairs(e.getValue());
        }
        System.out.println(ttl);
    }
    private static int getNumOfAnagramPairs(List<String> l){
        int ttl = 0;
        for(int i=0;i<l.size();i++){
            for(int j=i+1;j<l.size();j++){
                if(isAnagramPair(l.get(i),l.get(j))){
                    ttl++;
                }
            }
        }
        return ttl;
    }
    private static boolean isAnagramPair(String s1,String s2){
        char[] c1 = s1.toCharArray();
        Arrays.sort(c1);
        char[] c2 = s2.toCharArray();
        Arrays.sort(c2);
        s1 = new String(c1);
        s2 = new String(c2);
        return s1.equals(s2);
    }
}

Thursday, June 23, 2016

Distance to anagram:

Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency analysis with the books. He chooses strings

and

in such a way that

.
Your task is to help him find the minimum number of characters of the first string he needs to change to enable him to make it an anagram of the second string.
Note: A word x is an anagram of another word y if we can produce y by rearranging the letters of x.
Input Format
The first line will contain an integer,

, representing the number of test cases. Each test case will contain a string having length

, which will be concatenation of both the strings described above in the problem.The given string will contain only characters from

.
Output Format
An integer corresponding to each test case is printed in a different line, i.e. the number of changes required for each test case. Print

if it is not possible.
Constraints

Sample Input

6
aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

Sample Output

Explanation
Test Case #01: We have to replace all three characters from the first string to make both of strings anagram. Here,

= "aaa" and

= "bbb". So the solution is to replace all character 'a' in string a with character 'b'.

Test Case #02: You have to replace 'a' with 'b', which will generate "bb".

Test Case #03: It is not possible for two strings of unequal length to be anagram for each other.

Test Case #04: We have to replace both the characters of first string ("mn") to make it anagram of other one.

Test Case #05:

and

are already anagram to each other.

Test Case #06: Here S1 = "xaxb" and S2 = "bbxx". He had to replace 'a' from S1 with 'b' so that S1 = "xbxb" and we can rearrange its letter to "bbxx" in order to get S2.

Solution:
counting the presence of characters in first string, then reduce its counting by examining the second string. the sum of remaining numbers are the edit distance to make another anagram.

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for(int i=0;i<n;i++){
            System.out.println(solve(in.next()));
        }
                              
    }
    private static int solve(String s){
        if(s==null||s.length()%2==1)return -1;
        int[] cStatus = new int[26];
        for(int i=0;i<s.length()/2;i++){
            cStatus[s.charAt(i)-'a']++;
        }
        for(int i=s.length()/2;i<s.length();i++){
            if(cStatus[s.charAt(i)-'a']>0)
                cStatus[s.charAt(i)-'a']--;
        }
        int sum = 0;
        for(int i:cStatus)
            sum+=i;
        return sum;
    }
}