Short Palindrome Discussions | Algorithms | HackerRank
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. Search
  4. Short Palindrome
  5. Discussions

Short Palindrome

Sort by

recency

|

64 Discussions

|

  • mhuang005
     + 0 comments

    Python 3 solution

    This problem is similar to Count Triplets

    import string

    from collections import defaultdict

    def shortPalindrome(s): # Write your code here

    # frequency of characters
chars = defaultdict(int) 
# frequency of substrings 'ij', e.g. pair['ij'] = 2
pairs = defaultdict(int) 
# frequency of substrings 'iJJ'
triples = defaultdict(int)
mod = 10**9 + 7
count = 0

for j in s:
    # triples[j] is the total number of substrings of 'jAA'
    # we have seen so far
    # e.g., 'jaa', 'jbb', 'jcc' etc, starting with 'j'
    count += triples[j]

    for i in set(string.ascii_lowercase):   
        triples[i] += pairs[i+j]
        pairs[i+j] += chars[i]

    chars[j] += 1    

return count % mod

  • dehaka
     + 0 comments

    standard dynamic programming algo, O(n), but uses a lot of memory (couple hundred MBs). pass all test

    long pairPalindrome(int i, int j, const vector<vector<int>>& count) {
    if (i >= j) return 0;
    long sum = 0;
    for (int k=0; k < 26; k++) sum = (sum + ((count[j][k] - count[i-1][k]) * (count[j][k] - count[i-1][k] - 1) / 2)) % 1000000007;
    return sum;
}

long shortPalindrome(const string& s) {
    vector<int> TEMP1(26), TEMP2(26);
    vector<vector<int>> count = {TEMP1}, mostRecent = {TEMP2};
    for (int i=1; i <= s.size(); i++) {
        TEMP1[s[i-1]-'a']++;
        count.push_back(TEMP1);
        mostRecent.push_back(TEMP2);
        TEMP2[s[i-1]-'a'] = i;
    }
    long total = 0;
    vector<long> result(s.size()+1);
    vector<vector<int>> cache(s.size()+1, vector<int>(26));
    for (int i=1; i <= s.size(); i++) {
        int index = mostRecent[i][s[i-1]-'a'];
        if (index == 0) continue;
        result[i] = result[index] + (count[index][s[i-1]-'a']-1) * pairPalindrome(index, i-1, count) + pairPalindrome(index+1, i-1, count);
        for (int k=0; k < 26; k++) {
            result[i] = (result[i] + (long)cache[index][k] * (count[i-1][k] - count[index-1][k])) % 1000000007;
            cache[i][k] = (cache[index][k] + (long)(count[index][s[i-1]-'a']-1)*(count[i-1][k] - count[index-1][k])
                          + count[i-1][k] - count[index][k]) % 1000000007;
        }
        total = (total + result[i]) % 1000000007;
    }
    return total;
}

  • shreyavishwalin1
     + 0 comments
    def shortPalindrome(s):
  arr1 = [0]*26
  arr2 = [[0]*26 for i in range(26)]
  arr3 = [0]*26
  ans = 0
  for i in range(len(s)):
      idx = ord(s[i]) - ord('a')
      ans += arr3[idx]
      for j in range(26):
          arr3[j] += arr2[j][idx]
      for j in range(26):
          arr2[j][idx] += arr1[j]
      arr1[idx] += 1
  return ans % (10**9+7)

  • ihorfinance
     + 0 comments

    C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star :) )

    static size_t const alphabetSize{26};
static size_t const aASCII{97};
static size_t const modulo{static_cast<size_t>(std::pow(10, 9)) + 7};

size_t shortPalindrome(
    std::string const & str
){
    using namespace std;
    size_t tuplesCount = 0;
    auto char1{vector<size_t>(alphabetSize, 0)}; 
    auto chars12{vector<size_t>(alphabetSize * alphabetSize, 0)}; 
    auto chars123{vector<size_t>(alphabetSize, 0)};
    size_t chNum{0};
    size_t chCopy{0};
    for(auto const & ch: str){
        chNum = static_cast<size_t>(ch) - aASCII;
        chCopy = chNum;
        tuplesCount = (tuplesCount % modulo) + chars123.at(chCopy);
        for(auto i = 0; i < alphabetSize; ++i){
            chars123.at(i) += chars12.at(chCopy);
            chars12.at(chCopy) += char1.at(i);
            chCopy += 26;
        }
        ++char1.at(chNum);
    } 
    return tuplesCount % modulo;
}

  • JathOsh
     + 0 comments
    const alphabet = "abcdefghijklmnopqrstuvwxyz".split("")
const mod = (10 ** 9 + 7)
function shortPalindrome(s: string): number {
    let total = 0;
    
    // i
    const firstCharCount: Record<string, number> = {};
    // ij
    const charPairCount: Record<string, number> = {};
    // ijj
    const charDoublePairCount: Record<string, number> = {};
    
    for(const currChar of s){
        for(const char of alphabet){
            const ij = char + currChar; 
            const ijj = char + currChar + currChar; 
            const ijji = currChar + char + char;
            
            total += charDoublePairCount[ijji] || 0;
            total = total % mod;
            
            if(!charDoublePairCount[ijj])
                charDoublePairCount[ijj] = 0
            charDoublePairCount[ijj] += charPairCount[ij] || 0;
            charDoublePairCount[ijj] = charDoublePairCount[ijj] % mod;
            
            if(!charPairCount[ij])
                charPairCount[ij] = 0
            charPairCount[ij] += firstCharCount[char] || 0;
            charPairCount[ij] = charPairCount[ij] % mod;
        }
        if(!firstCharCount[currChar])
            firstCharCount[currChar] = 0;
        firstCharCount[currChar] += 1;
        firstCharCount[currChar] = firstCharCount[currChar] % mod;
    }
    return total;
}