[!NOTE]
この記事は 2013/06/30 に momoto.github.io へ投稿した内容を Qiita へ移行してきたものです
getEqualSumSubstring 関数の問題を考えてみます。この問題の出典についてはわかりませんが、Stack Overflow 等で少し話題になったようです。
問題
Complete the function getEqualSumSubstring, which takes a single argument. The single argument is a string
s
, which contains only non-zero digits. This function should print the length of longest contiguous substring ofs
, such that the length of the substring is 2*N digits and the sum of the leftmost N digits is equal to the sum of the rightmost N digits. If there is no such string, your function should print 0.
参考訳
0 以外の数字だけを含む文字列
s
を引数にとる getEqualSumSubstring 関数を定義します。
この関数は、文字列s
から次の条件に当てはまる最も長い部分列の長さを表示します。部分列は、長さが 2*N であり、左側 N 個の数字の合計と右側 N 個の数字の合計が等しくなることが条件です。適当な部分列がない場合には0と表示します。
例1)入力された文字列が 123231
であるとき、連続する最も長い部分列は 123231
で、関数が出力する部分列の長さは 6
になります。
例2)入力された文字列が 986561517416921217551395112859219257312
であるとき、連続する最も長い部分列は 656151741692121755139511285921925731
で、関数が出力する部分列の長さは 36
になります。
解答例
まず、ナイーブに思いつくのは、長さが偶数になる部分列だけを s
から抜き出して配列に格納しておいて、次に、部分列の左側半分の数字の合計と右側半分の数字の合計が等しくなるような部分列の最も長いものを配列から探すことです。
仮に入力された文字列が 986561517416921217551395112859219257312
がであれば配列は ["98", "9865", "986561" ... "86", "8656", "865615" ...]
というようにします。以下は JavaScript による解答例です。
function getEqualSumSubstring(s) {
var substrings = [], longest = "";
for (var begin=0; begin<s.length; begin++)
for (var end=begin+2; end<=s.length; end=end+2)
substrings[substrings.length] = s.slice(begin, end);
for (var i in substrings)
if (substrings[i].length <= longest.length)
continue;
else if ((function (s) {
var begin=0, end=s.length/2, left=0, right=0;
for (begin; begin<end; begin++) {
left += parseInt(s[begin]);
right += parseInt(s[end + begin]);
}
return (left === right);
})(substrings[i]))
longest = substrings[i];
return longest.length;
}
別解
上の解答例では、部分列の短い順に適当な部分列を探していましたが、部分列の長い順に探した方が効率的であることは問題文から明らかです。部分列の長い順に探索することで、左側半分と右側半分の数字の合計が等しい部分列を見つけ次第、処理を終了することができます。
function getEqualSumSubstring(s) {
var substring="";
for (var end=s.length-s.length%2; end>0; end=end-2)
for (var begin=0; s.length>=(begin+end); begin++)
if ((function (s) {
var begin=0, end=s.length/2, left=0, right=0;
for (begin; begin<end; begin++) {
left += parseInt(s[begin]);
right += parseInt(s[end + begin]);
}
return (left === right);
})(substring = s.slice(begin, (end+begin))))
return substring.length;
return 0;
}