Find the max length of the substring in a digit string that its sum of the first half is equal to its second half #DPfCI #dynamic_programming

bruteforce.cpp

#include <cassert>
#include <iostream>
#include <string>

bool
IsHalfEqual(std::string s)
{
  assert(s.length() % 2 == 0);

  unsigned int i = 0;
  unsigned a = 0, b = 0;
  for (; i < s.length() / 2 ; ++i) {
    assert(s.at(i) >= '0' && s.at(i) <= '9');
    a += s.at(i) - '0';
  }

  for (; i < s.length() ; ++i) {
    assert(s.at(i) >= '0' && s.at(i) <= '9');
    b += s.at(i) - '0';
  }

  return a == b;
}

// unsigned int
// MaxLength(std::string s)
// {
//   unsigned int max = 0;
//   for (unsigned int l = 2; l <= s.length() ; l = l + 2) {
//     for (unsigned int p = 0 ; p <= s.length() - l ; ++p) {
//       if (IsHalfEqual(s.substr(p, l))) {
//         // std::cout << s.substr(p, l) << std::endl;
//         max = l;
//       }
//     }
//   }

//   return max;
// }

// unsigned int
// MaxLength(std::string s)
// {
//   unsigned int max = 0;
//   for (unsigned int i = 0 ; i < s.length() ; ++i) {
//     for (unsigned int j = i + 1 ; j < s.length() ; j += 2) {
//       unsigned int len = j - i + 1;
//       if (IsHalfEqual(s.substr(i, len))) {
//         // std::cout << s.substr(i, len) << std::endl;
//         if (len > max) {
//           max = len;
//         }
//       }
//     }
//   }

//   return max;
// }

unsigned int
MaxLength(std::string s)
{
  unsigned int max = 0;
  for (unsigned int i = 0 ; i < s.length() ; ++i) {
    // Accumilate j by 2 since it must be a even number.
    // After max is updated, we need to jump to j, where
    // j - i + 1 >= max + 2, so j = max + i + 1.
    for (unsigned int j = max + i + 1 ; j < s.length() ; j += 2) {
      unsigned int len = j - i + 1;
      if (IsHalfEqual(s.substr(i, len))) {
        // std::cout << s.substr(i, len) << std::endl;
        if (len > max) {
          max = len;
        }
      }
    }
  }

  return max;
}

int main()
{
  // std::string s("9430723");
  // std::string s("142421");
  std::string s("0932314264093628421563223");
  std::cout << "max len is " << MaxLength(s) << std::endl;

  return 0;
}

dp.cpp

#include <cassert>
#include <iostream>
#include <string>
#include <vector>

unsigned int
MaxLength(std::string s, std::vector< std::vector<unsigned int> >& sum)
{
  assert(sum.size() >= s.length());

  for (unsigned int i = 0 ; i < sum.size() ; ++i) {
    assert(sum[i].size() >= s.length());
    assert(s.at(i) >= '0' && s.at(i) <= '9');
    sum[i][i] = s.at(i) - '0';
  }

  unsigned int max = 0;
  for (unsigned int l = 2 ; l <= sum.size() ; ++l) {
    for (unsigned int i = 0 ; i <= sum.size() - l ; ++i) {
      unsigned int k = l / 2;
      unsigned int j = i + l - 1;
      unsigned int m = j - k;
      sum[i][j] = sum[i][m] + sum[m + 1][j];
      if (l % 2 == 0 && sum[i][m] == sum[m + 1][j] && l > max) {
        max = l;
      }
    }
  }

  return max;
}

unsigned int
MaxLength(std::string s)
{
  // sum[i][j] = summation of the digits from position i to j in the string.
  std::vector< std::vector<unsigned int> >
    sum(s.length(), std::vector<unsigned int>(s.length(), 0));
  return MaxLength(s, sum);
}

int main()
{
  // std::string s("9430723");
  // std::string s("142421");
  std::string s("0932314264093628421563223");
  std::cout << "max len is " << MaxLength(s) << std::endl;

  return 0;
}