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

|

65 Discussions

|

  • radoslav_vecera
     + 0 comments

    inline int I(const char i){return i-'a';} // convert character into index 'a'=0 ..

    inline void SUM(long & s,long & x){s = (s + x)% 1000000007;} // add x into s with modulo

    int shortPalindrome(string s) {

    long count = 0;

constexpr int l_count='z'-'a'+1;

long c3[l_count]={0}; // c3[x] count of previous tri-characters starting with x

long c2[l_count][l_count]={0}; // c2[x][y] count of duo-characters xy, e.g. c2[0][1] = count of "ab"

long c1[l_count]={0};// count of each character so far.

for (auto & x:s)

{
    SUM(count,c3[I(x)]); // add count of all tri-characters which need x to complete palindrome.

    for (int i=0;i<l_count;++i)

    {
        SUM(c3[i],c2[i][I(x)]); // add new combinations of tri-characters which could be created from due-characters by adding x.

    }
    for (int i=0;i<l_count;++i)

    {
        SUM(c2[i][I(x)],c1[i]); // add new combinations of duo-characters which could be created from single characters by adding x

    }
    ++c1[I(x)];// increase count of single characters of x

}
return count;

    }

  • 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;
}