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. Maximum Palindromes
  5. Discussions

Maximum Palindromes

  • alday
     + 0 comments

    The only trick here is to cache the frequency map, since you are going to use it for every single test in the test-range. Do not bother caching modinverse, etc. The real cost is the string manipulation. Do something like this in your initialize function

      std::vector<std::vector<int>> s_cumulativeFreq;

  void initialize(std::string s)
  {
    std::vector<std::vector<int>>(s.size()+1, std::vector<int>(26, 0)).swap(s_cumulativeFreq);
    for (size_t i = 0; i < s.size(); ++i) {
      auto& prevFreq = s_cumulativeFreq[i];
      auto& currFreq = s_cumulativeFreq[i + 1];
      std::copy(prevFreq.begin(), prevFreq.end(), currFreq.begin());
      ++currFreq[s[i] - 'a'];
  }
 }

    And of course, calculate the difference in frequencies...

    int answerQuery(int first, int last)
{
  auto len = last - first + 1;
  if (len == 1)
    return 1;

  std::vector<int> freqs = s_cumulativeFreq[last];  // Compute the frequencies in the range [l, r)
  {
    auto leftIter = next(s_cumulativeFreq.begin(), first - 1); // I want to remove the entries BEFORE 'first'
    transform(freqs.begin(), freqs.end(), leftIter->begin(), freqs.begin(), std::minus<int>()); // Compute the frequencies in the range [l, r]
  }

  auto middleChars = std::count_if(freqs.begin(), freqs.end(), [](int f) {return f & 1; });
  // Now I divide by 2. I only care about the left side of the palindrome
  for_each(freqs.begin(), freqs.end(), [](auto& f) {f >>= 1; });
  freqs.erase(std::remove(freqs.begin(), freqs.end(), 0), freqs.end());
  // Total number of chars to permutate...
  auto palindromeChars = accumulate(freqs.begin(), freqs.end(), 0, std::plus<int>());
  ...
  You can fill the rest
  ...