CareerCup

calculate even, odd sum(ascii) and compute a hash for it. Answer will the number of different hashes generated.

from collections import Counter
def count(arr):
    fs = [(tuple(Counter(x[::2]).items()), 
    	     (tuple(Counter(x[1::2]).items()))) 
    	     for x in arr]
    return sum(z for (x,z) in Counter(fs).items() if z>1)
    
print count(["abcd","cbad","bacd"])
print count(["abcd", "acbd", "adcb", "cdba",
"bcda", "badc"])

class SpecialEquivalient {

    private int count = 0;

    SpecialEquivalient (String[] input) {
        Set<String> outputSet = new HashSet<String>();;
        for(String str : input) {
            String[] evenOdd = splitEvenOdd(str);
            String sortedString = sortString(evenOdd[0]) + sortString(evenOdd[1]);
            outputSet.add(sortedString);
        }
        count = outputSet.size();
    }

    String[] splitEvenOdd(String str) {
        char[] chars = str.toCharArray();
        String odd = new String();
        String  even = new String();
        for (int i=0; i<str.length(); i++) {
            if (i % 2 == 1) {
                odd += chars[i];
            } else {
                even += chars[i];
            }
        }
        return new String[] {odd, even};
    }

    String sortString(String str) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        return new String(charArray);
    }

    public int uniqueCount() {
        return count;
    }
}

public class Main {

    public static void main(String[] args) {

        // test set
//        String[] arr = {"abcd", "cbad", "bacd"};
        String[] arr = {"abcd", "acbd", "adcb", "cdba", "bcda", "badc"};

        // convert ArrayList form as it is beneficial to handle
        ArrayList<String> input = new ArrayList<String>();
        for (int i = 0; i <arr.length; i++) {
            input.add(i, arr[i]);
        }

        // main loop
        for (int i = 0; i < input.size()-1; i++) {

            for (int j = i+1; j < input.size(); j++) {

                // Question here: any possibility that identical strings exist? (assuming no for now)

                // check with swapEven
                if (input.get(i).equals(swapEven(input.get(j)))) {
                    // remove if equivalent
                    input.remove(j);
                    j--;
                    // go back to loop
                    continue;
                }

                // check with swapOdd
                if (input.get(i).equals(swapOdd(input.get(j)))) {
                    // remove if equivalent
                    input.remove(j);
                    j--;
                    // go back to loop (no need as this is end of loop)
                    //continue;
                }
            }

        }

        System.out.println("length: " + input.size());
    }

    // swap a character at even-numbered index
    // assuming string length is 4
    static String swapEven(String in) {

        char data[] = {in.charAt(2), in.charAt(1), in.charAt(0), in.charAt(3)};
        String out = new String(data);

        return out;
    }

    // swap a character at odd-numbered index
    // assuming string length is 4
    static String swapOdd(String in) {

        char data[] = {in.charAt(0), in.charAt(3), in.charAt(2), in.charAt(1)};
        String out = new String(data);

        return out;
    }
}

#!/usr/bin/env python
import collections

class Soln(object):
def encode(self, s):
print s

mapodd = [0]*26
mapeven = [0] * 26
encodestr = ""

for i in range(len(s)):
c = s[i]
if i&1:
mapodd[ord(c) - ord('a')] += 1
else:
mapeven[ord(c) - ord('a')] += 1

for i in range(26):
encodestr += str(mapeven[i])
encodestr += str(ord('-'))
encodestr += str(mapodd[i])
encodestr += str(ord('-'))

print encodestr
return encodestr

def distictWords(self, words):
lw = len(words)
if lw == 0:
return 0
ordset = collections.defaultdict(int)
for i in range(lw):
encodestr = self.encode(words[i])
ordset[encodestr] += 1

print ordset
return len(ordset)

soln = Soln();
print soln.distictWords(["abcd", "cbad", "dbac"])
print soln.distictWords(["abcd", "cbad"])
print soln.distictWords(["abcd", "acbd", "adcb", "cdba", "bcda", "badc"])

For each string, sort all even characters among themselves. For each string, sort all odd characters among themselves. Then start putting the strings in a hashmap. For example, if String s1 after sorting matches string s2, s1 is key and s2 is part of a list which is value of s1. Repeat for any strings which do not match.

This is typical example of hashing with user defined Hash function.

Just generate a hash based on index and then count distinct string by Hash.

static String encodeString(char[] str) { 
        // hashEven stores the count of even indexed character 
        // for each string hashOdd stores the count of odd 
        // indexed characters for each string 
        int hashEven[] = new int[MAX_CHAR]; 
        int hashOdd[] = new int[MAX_CHAR]; 
  
        // creating hash for each string 
        for (int i = 0; i < str.length; i++) { 
            char c = str[i]; 
            if ((i & 1) != 0) // If index of current character is odd 
                hashOdd[c-'a']++; 
            else
                hashEven[c-'a']++; 
  
        } 
  
  
        // For every character from 'a' to 'z', we store its 
        // count at even position followed by a separator, 
        // followed by count at odd position. 
        String encoding = ""; 
        for (int i = 0; i < MAX_CHAR; i++) { 
            encoding += (hashEven[i]); 
            encoding += ('-'); 
            encoding += (hashOdd[i]); 
            encoding += ('-'); 
        } 
        return encoding; 
    }

A hash function.


Just iterate and convert to hash, put in set if not present then increase count otherwise skip

/*
Problem is that:
 swap_even() can permutate only even indices.
 swap_odd() can permutate only odd indices.
That means that if someone breaks down the word into 
two bag of characters with 
Even [0] Bag for even indices ( 0 based indexing )
Odd [1] Bag of odd indices 
Then, two words are equivalent if 
for word w1 and w2
the bags ( Even and Odd ) are comprise of exact same 
characters with exact same frequencies
that is the tuple ( char , count ) must be same 
But on introspection, we can not compare this dictionary tuples.
So, what we do is create a sorted charset and then put a delimiter
to ensure that sorted_even_chars # sep # sorted_odd_chars
acts as key 

Thus, we can create a hash function that is entirely reliant on that.
 */

 def special_equivalent_hash_function( string ){
   #(even, odd) = partition( string.toCharArray ) where { 2 /? $.i }
   sorted_evens = str( sorta(even), '') 
   sorted_odds = str( sorta(odd), '') 
   sorted_evens + "#" +  sorted_odds // return  
 }

def find_all_special_equivalents( list_of_strings ){
  mset( list_of_strings ) as {
    special_equivalent_hash_function( $.o )
  }
}

res = find_all_special_equivalents( ["abcd", "cbad", "bacd" ] )
println( jstr(res,true) )

Produces :

{
        "ac#bd":[
                "abcd",
                "cbad"
        ],
        "bc#ad":[
                "bacd"
        ]
}

def main():
    strAr = ["abcd", "cbad", "efgh", "cdab"]
    
    searchAr = strAr.copy()
    
    count = 0
    countEven, countOdd = 0,0
    total = 0
    
    for str in strAr:
        l1 = list(str)
        searchAr = strAr.copy()
        searchAr.remove(str)
        countEven = search(l1,searchAr, count, 0)
        countOdd = search(l1,searchAr, count, 1)
        
        total += countEven + countOdd

    print ("total : ", total)

def search(l1, searchAr, count, start):
    
    total = 0
    
    i = start
    
    for i in range(0,len(l1)-1,2):
        for j in range (i+2,len(l1)-1,2):
            s = l1[i]
            l1[i] = l1[j]
            l1[j] = s
            count = getCount(l1, searchAr, count)
            total += count
            
    return total

def getCount(l1, searchAr, count):
    
    s1 = "".join(l1)
    
    print("getCount")
    print(s1)
    print(searchAr)
    
    for s in searchAr:
        if (s1 == s):
            count += 1
    
    print(count)
    
    return count

main()

Just split one Stirng (a1b1a2b2a3b3.....) to two sets of odd and even (a1, a2, a3 ...) and (b1, b2, b3...). Sort them and put the two sorted together.

Count the unique strings as processed above.
Based on the theory that for a given sequence (a1, a2, a3 .... an)
ALL n! permutations can be get by exchange ax and ay (1<=x<=y<=n). This can be easily proven by Mathematical Induction.

code:

public class TwoSwapString {

    public static void main(String[] arug) {
        int n = 0;
        n = count(new String[]{"abcd","cbad","bacd"});
        System.out.println(n);
        n = count(new String[]{"abcd", "acbd", "adcb", "cdba","bcda", "badc"});
        System.out.println(n);
    }

    private static int count(String[] strings) {
        HashSet<String> result = new HashSet<>();
        for (int i=0; i<strings.length; i++) {
            String s = strings[i];
            String even = "";
            String odd = "";
            for (int j=0; j<s.length(); j++) {
                if (j % 2 == 0) {
                    even += s.charAt(j);
                } else {
                    odd += s.charAt(j);
                }
            }
            even = toString(even.toCharArray());
            odd = toString(odd.toCharArray());
            result.add(even + "," + odd);
        }

        System.out.println(result);

        return result.size();
    }

    private static String toString(char[] chars) {
        Arrays.sort(chars);
        return new String(chars);
    }
}