We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Sherlock and Anagrams
  2. Discussions

Sherlock and Anagrams

Sort by

recency

|

28 Discussions

|

  • kocsis_tamas_ol1
     + 0 comments

    I thought to use a double for loop, so we start from every position, grow every size of substring until end of string, sort it, and store the substring. When we find a pair, we count up.

    cdcd expected output=5. Why? substring sorted their count when more than 1: c:2 d:2 cd: 3

  • jimiwills
     + 0 comments
    public static int sherlockAndAnagrams(string s)
{
    var allAnagrammaticPairs = 0;
    for(var l = 1; l < s.Length; l++){
        var d = new Dictionary<string, int>();
        for(var i=0; i<s.Length-l+1; i++){
            var ss = new string(s.Substring(i, l).ToCharArray().Order().ToArray());
            if(! d.ContainsKey(ss)) d[ss] = 0;
            d[ss]++;
        }
        var v = d.Values.Where(x => x > 1);
        var combinations = v.Select(x => (x-1)*x/2);
        allAnagrammaticPairs += combinations.Sum();
    }
    return allAnagrammaticPairs;
}

  • xeusclay
     + 0 comments
    from collections import defaultdict

def sherlockAndAnagrams(s):
    def get_frequency_hash(freq):
        return tuple(freq)

    n = len(s)
    anagram_count = 0
    freq_map = defaultdict(int)

    # Calculate cumulative frequency for each position
    cum_freq = [[0] * 26 for _ in range(n + 1)]
    for i in range(1, n + 1):
        cum_freq[i] = cum_freq[i-1][:]
        cum_freq[i][ord(s[i-1]) - ord('a')] += 1

    # Count frequency differences
    for length in range(1, n):
        freq_map.clear()
        for i in range(n - length + 1):
            j = i + length
            freq_diff = [cum_freq[j][k] - cum_freq[i][k] for k in range(26)]
            freq_hash = get_frequency_hash(freq_diff)
            freq_map[freq_hash] += 1

        # Calculate anagram pairs
        for count in freq_map.values():
            anagram_count += count * (count - 1) // 2

    return anagram_count

  • vadym_usatiuk
     + 0 comments

    Java

    public static int sherlockAndAnagrams(String s) {
        int count = 0;
        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String substring = s.substring(i, j);
                char[] chars = substring.toCharArray();
                Arrays.sort(chars);
                String sortedSubstring = new String(chars);

                map.put(sortedSubstring, map.getOrDefault(sortedSubstring, 0) + 1);
            }
        }

        for (int value : map.values()) {
            count += value * (value - 1) / 2; // combination formula is n * (n - 1) / 2
        }

        return count;
    }

  • vitorio_tfm
     + 0 comments

    Java

        public static int sherlockAndAnagrams(String s) {
        Map<String, Integer> occurrences = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String val = sortString(s.substring(i, j + 1));
                occurrences.put(val, occurrences.getOrDefault(val, 0) + 1);
            }
        }
        int anagramPairCount = 0;
        occurrences = removeSingleOccurrences(occurrences);
        for (Map.Entry<String, Integer> e : occurrences.entrySet()) {
            // Once occurrence ‘o’ of each frequency array is stored, total anagrams will be the sum of
            // o*(o-1)/2 for all different frequency arrays because if a particular substring has ‘o’ anagrams in
            // string total o*(o-1)/2 anagram pairs can be formed. Below is the implementation of above idea.

            // The division by two is needed to disregard different combinations between two elements:
            // [0, 1] and [1, 0]
            anagramPairCount += (e.getValue() * (e.getValue() - 1)) / 2;
        }
        return anagramPairCount;
    }

    private static Map<String, Integer> removeSingleOccurrences(Map<String, Integer> occurrences) {
        return occurrences
            .entrySet()
            .stream()
            .filter(e -> e.getValue() > 1)
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
    }

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