fork download
copy 
  1. /*
  2.     Problem: Sum of Palindrome Rearrangement Costs of All Substrings
  3.     Company Tag: Intuit OA
  4.  
  5.     Problem Statement:
  6.         We are given a string s.
  7.  
  8.         For any substring, cost is the minimum number of character replacements
  9.         needed so that the substring can be rearranged to form a palindrome.
  10.  
  11.         A string can be rearranged into a palindrome if at most one character
  12.         has odd frequency.
  13.  
  14.         If oddCount is number of characters with odd frequency:
  15.             cost = oddCount / 2
  16.  
  17.         Return sum of costs over all substrings.
  18.  
  19.     Constraints:
  20.         1 <= s.length <= 200000
  21.         s consists of lowercase English letters.
  22.  
  23.     Brute Force:
  24.         Generate every substring and count character frequencies.
  25.  
  26.     Why Brute Force Fails:
  27.         There are O(n^2) substrings.
  28.  
  29.     Optimized Idea:
  30.         Use prefix parity mask.
  31.  
  32.         For every prefix:
  33.             bit c = 1 means character c has odd frequency till now.
  34.  
  35.         For substring l to r:
  36.             odd mask = prefix[r + 1] XOR prefix[l]
  37.  
  38.         Number of odd characters:
  39.             popcount(odd mask)
  40.  
  41.     Explanation Block:
  42.         For every pair of prefix masks, we need:
  43.             floor(popcount(mask1 XOR mask2) / 2)
  44.  
  45.         Formula:
  46.             floor(x / 2) = (x - (x % 2)) / 2
  47.  
  48.         So I calculate:
  49.             1. Total Hamming distance over all prefix mask pairs.
  50.             2. Number of pairs having odd Hamming distance.
  51.  
  52.         Answer:
  53.             (totalHammingDistance - oddHammingPairs) / 2
  54.  
  55.     Dry Run:
  56.         s = "abc"
  57.  
  58.         Substrings:
  59.             "a"   -> cost 0
  60.             "b"   -> cost 0
  61.             "c"   -> cost 0
  62.             "ab"  -> cost 1
  63.             "bc"  -> cost 1
  64.             "abc" -> cost 1
  65.  
  66.         Total = 3
  67.  
  68.     Time Complexity:
  69.         O(26 * n)
  70.  
  71.     Space Complexity:
  72.         O(n)
  73. */
  74.  
  75. #include <bits/stdc++.h>
  76. using namespace std;
  77.  
  78. using ll = long long;
  79.  
  80. long long sumPalindromeRearrangementCosts(string s) {
  81.     int n = s.size();
  82.  
  83.     vector<int> prefixMasks;
  84.     prefixMasks.reserve(n + 1);
  85.  
  86.     int mask = 0;
  87.  
  88.     // Empty prefix mask.
  89.     prefixMasks.push_back(mask);
  90.  
  91.     for (char ch : s) {
  92.         int bit = ch - 'a';
  93.  
  94.         // Toggle parity of current character.
  95.         // Even frequency becomes odd.
  96.         // Odd frequency becomes even.
  97.         mask ^= (1 << bit);
  98.  
  99.         prefixMasks.push_back(mask);
  100.     }
  101.  
  102.     long long totalHammingDistance = 0;
  103.  
  104.     // For each character bit:
  105.     // Count how many prefix masks have bit 0 and bit 1.
  106.     // Every pair with different bit value contributes 1 to Hamming distance.
  107.     for (int bit = 0; bit < 26; bit++) {
  108.         long long ones = 0;
  109.         long long zeros = 0;
  110.  
  111.         for (int m : prefixMasks) {
  112.             if (m & (1 << bit)) {
  113.                 ones++;
  114.             } else {
  115.                 zeros++;
  116.             }
  117.         }
  118.  
  119.         totalHammingDistance += ones * zeros;
  120.     }
  121.  
  122.     long long evenParityMasks = 0;
  123.     long long oddParityMasks = 0;
  124.  
  125.     // If two masks have different popcount parity,
  126.     // their XOR has odd Hamming distance.
  127.     for (int m : prefixMasks) {
  128.         if (__builtin_popcount((unsigned int)m) % 2 == 0) {
  129.             evenParityMasks++;
  130.         } else {
  131.             oddParityMasks++;
  132.         }
  133.     }
  134.  
  135.     long long oddHammingPairs = evenParityMasks * oddParityMasks;
  136.  
  137.     // Applying:
  138.     // floor(x / 2) = (x - (x % 2)) / 2
  139.     long long answer = (totalHammingDistance - oddHammingPairs) / 2;
  140.  
  141.     return answer;
  142. }
  143.  
  144. int main() {
  145.     string s = "abc";
  146.  
  147.     cout << sumPalindromeRearrangementCosts(s) << endl;
  148.  
  149.     return 0;
  150. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/nP0L2e
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!