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. Prepare
  2. Algorithms
  3. Strings
  4. Sherlock and Anagrams
  5. Discussions

Sherlock and Anagrams

Sort by

recency

|

1701 Discussions

|

  • rajivaiyer
     + 0 comments

    My Java 8 solution, which passes all test cases, with max score = 50:

    The basic idea is as follows:

    (1) Iterate through the entire string once, and for each new / distinct character encountered, accumulate the List of Indices where the character occurs into LinkedHashMap<Character, List<Integer>> chIdxMap.

    (2) Iterate through all the Character Keys in LinkedHashMap<Character, List<Integer>> chIdxMap, and for each character: the Number of "Single Character Anagrams" (i.e. "aaa", "bbbb", etc) = (n * (n - 1)) / 2, where 'n' is the number of occurences of the character in the string.

    (3) Iterate through the string again, and for each Character at each Index, start from "Anagram Length = 2", and search for all Anagrams of that Length. And keep incrementing Anagram Length by 1 at each iteration.

    (Ignore the verbose debug print statements. Those were added to test the logic before submission, and have been commented out once solution was finalized & verified that everything passed).

    class Result {
    public static boolean areAnagrams(String x, String y) {
        // Early exit: lengths must match for anagrams
        if (x.length() != y.length()) {
            return false;
        }

        // Frequency maps for both strings
        Map<Character, Long> xFreq = x.chars()
                                      .mapToObj(c -> (char) c)
                                      .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        Map<Character, Long> yFreq = y.chars()
                                      .mapToObj(c -> (char) c)
                                      .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        return xFreq.equals(yFreq);
    }

    public static boolean containsOtherThanTarget(List<Integer> intLst, 
                                                  int target) {
        return intLst.stream().anyMatch(x -> x != target);
    }

    public static List<Integer> findAllCharOccurrences(String input, char target) {
        List<Integer> indices = new ArrayList<>();

        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == target) {
                indices.add(i);
            }
        }

        return indices;
    }

    /*
     * Complete the 'sherlockAndAnagrams' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int sherlockAndAnagrams(String s) {
        // Write your code here
        int numAnagramPairs = 0;
        
        // System.err.println(""); System.err.println("");
        // System.err.println("s = >" + s + "<");

        LinkedHashMap<Character, List<Integer>> chIdxMap = new LinkedHashMap<>();
        for (int sIdx = 0 ; sIdx < s.length() ; sIdx++) {
            if (!chIdxMap.containsKey(s.charAt(sIdx))) {
                chIdxMap.put(s.charAt(sIdx), 
                             findAllCharOccurrences(s, s.charAt(sIdx)));
            }
        }
        // System.err.println("chIdxMap = >" + chIdxMap + "<");
        
        for (Character chKey : chIdxMap.keySet()) {
            List<Integer> curChIdxLst = chIdxMap.get(chKey);
            int n = curChIdxLst.size();
            int numSingChAnag = (n * (n-1)) / 2;
            // System.err.println("chKey = >" + chKey + "< | curChIdxLst.size() = >" + 
            //                    curChIdxLst.size() + "< | numSingChAnag = >" + 
            //                    numSingChAnag + "<");
            numAnagramPairs += numSingChAnag;
        }
        // System.err.println("After Single Char Anagram Pair Computation :: " + 
        //                    "numAnagramPairs = >" + numAnagramPairs + "<");

        for (int sIdx = 0 ; sIdx < s.length() ; sIdx++) {
            List<Integer> curChIdxLst = chIdxMap.get(s.charAt(sIdx));
            // System.err.println("curChIdxLst = >" + curChIdxLst + "<");

            if (curChIdxLst.size() == 1 || 
                !containsOtherThanTarget(curChIdxLst, sIdx)) {
                continue;
            }

            for (int anaStrLen = 2; (sIdx + anaStrLen) <= s.length() ; anaStrLen++ ) {
                String selSubStrSrc = s.substring(sIdx, sIdx + anaStrLen);
                // System.err.println("selSubStrSrc = >" + selSubStrSrc + "<" +
                //                    " from (" + sIdx + ", " + (sIdx + anaStrLen - 1) + ")");

                for (int cIdx = (sIdx + 1) ; (cIdx + anaStrLen) <= s.length() ; cIdx++) {
                    String selSubStrTgt = s.substring(cIdx, cIdx + anaStrLen);
                    // System.err.println("selSubStrTgt = >" + selSubStrTgt + "<" +
                    //                    " from (" + cIdx + ", " + (cIdx + anaStrLen - 1) + ")");
                    if (areAnagrams(selSubStrSrc, selSubStrTgt)) {
                        // System.err.println("Anagram Found!");
                        numAnagramPairs++;
                    }
                }
            }
        }

        // System.err.println("numAnagramPairs = >" + numAnagramPairs + "<");
        return numAnagramPairs;
    }

}

  • mohammed_abrar_1
     + 0 comments

    import java.io.; import java.util.;

    class Result {

    /*
 * Complete the 'sherlockAndAnagrams' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts STRING s as parameter.
 */

public static int sherlockAndAnagrams(String s) {
    Map<String, Integer> freqMap = new HashMap<>();
    int n = s.length();

    // Generate all substrings
    for (int i = 0; i < n; i++) {
        int[] count = new int[26];
        for (int j = i; j < n; j++) {
            count[s.charAt(j) - 'a']++;
            StringBuilder key = new StringBuilder();
            for (int k = 0; k < 26; k++) {
                key.append(count[k]).append('#');
            }
            String signature = key.toString();
            freqMap.put(signature, freqMap.getOrDefault(signature, 0) + 1);
        }
    }

    int totalPairs = 0;
    for (int val : freqMap.values()) {
        totalPairs += (val * (val - 1)) / 2;
    }

    return totalPairs;
}

    }

    public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

    for (int qItr = 0; qItr < q; qItr++) {
        String s = bufferedReader.readLine();
        int result = Result.sherlockAndAnagrams(s);
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
    }

    bufferedReader.close();
    bufferedWriter.close();
}

    }

  • ikenna4
     + 0 comments

    Ruby solution:

    def sherlockAndAnagrams(s)
    substrings = Hash.new { |h,k| h[k] = 0 }
    (0..s.length - 1).each do |i|
        (i..s.length - 1).each do |j|
            sorted = s[i..j].chars.sort.join
            substrings[sorted] += 1
        end
    end
        
    substrings.values.
        filter { |f| f > 1 }.
        map { |k| k * (k - 1) / 2 }.
        sum
end

  • ajvnho
     + 0 comments

    A short CPP version:

    int sherlockAndAnagrams(std::string s) {
    std::map<std::map<char,int>, int> unique_strings;
    int result = 0;
    for (size_t i = 0; i<s.size(); ++i){
        std::map<char,int> submap;
        for (size_t j = i; j<s.size(); ++j) {
            submap[s[j]]++;
            unique_strings[submap]++;
        }
    }
    for (auto& [substr, count]: unique_strings) {
        result += (count - 1)* count / 2;
    }
    return result;
}

  • saberelharti
     + 0 comments

    Here's the approch that I implement to solve this problem with Kotlin: 

    fun sherlockAndAnagrams(s: String): Int {
    var windowedSize = s.length - 1 // define possible windowed steps for that string
    var listOfWindows : List<List<Char>> = listOf()
    var anagramsCounter = 0
    
    // itterate based on possible windowed steps
    while(windowedSize > 0){
        // get all windowed sets
        listOfWindows = s.toList().windowed(size = windowedSize, step = 1) { it ->
            it.sortedBy { it }
        }
        // count all anagrams
        listOfWindows.forEachIndexed{ index, window ->
            for(j in (index + 1) .. listOfWindows.lastIndex) {
                if(window == listOfWindows[j])  
                    anagramsCounter++
            }
        }
        windowedSize-- // reduce the windowed size
    }
    return anagramsCounter
}