文字列にk個のスワップを入れてp個のコンセプティブな文字を作る方法は？

Question

1'sと0'sの文字列があります（例：110001110）。私は2つの数字kとpを与えていると私はそれが1それ0とその逆作る場合、私はkスワップを行うことによって、[最大p連続し1'sか0'sを取得し、私が意味するスワップでできるかどうかを確認する必要があります。

EDIT-私は明確に説明していないと思います。 たとえば、文字列を1110000111とし、p = 3とk = 1とします。だから1回のスワップを行うことによって、私は1110010111に変えることができるので、答えがyesの1'sまたは0'sの3つのコンセプチブを得ることができます。

Answer 1

これは直線的なループで簡単に行うことができます。すべて0または1の単調なシーケンスを検出した後、簡単な数式で必要なフリップの数を計算します。これらのフリップは、pが1である場合を除いて、そのシーケンスの外側の数字が変更されないようにすることができます。その場合、反転は01010101 ...または101010101のいずれかにする必要があります....これは単純なモジュロ式でも行うことができます。 2人のうち最高の人が取られます（より少ないスワップ）。ここで

は、2つのサンプルとJavaScriptで実装が一般的な場合（P> 1）と述べた特殊なケースのために実行された（p = 1）：

function swapsForMaxSequence(s, maxSize) { 
 
    var head, tail, swaps; 
 

 
    if (maxSize < 1) return false; 
 
    
 
    swaps = 0; 
 
    if (maxSize === 1) { // Special case 
 
     // 0 and 1 should be alternating: 
 
     for (head = 0; head < s.length; head++) { // n iterations 
 
      if (Number(s[head]) == head % 2) swaps++; 
 
     } 
 
     // Either the made swaps or the opposite swaps would do it: 
 
     return Math.min(swaps, s.length - swaps); 
 
    } 
 
    tail = 0; 
 
    for (head = 1; head <= s.length; head++) { // n iterations 
 
     if (head === s.length || s[head] != s[tail]) { // end of sequence? 
 
      swaps += Math.floor((head - tail)/(maxSize+1)); 
 
      tail = head; // Start of new sequence 
 
     } 
 
    } 
 
    return swaps; 
 
} 
 

 
// Sample input: 
 
var s = '10110101010', // Special case 
 
    k = 1, 
 
    p = 1; 
 

 
// Display input: 
 
console.log('s:', s, 'k:', k, 'p:', p); 
 

 
// Run the algorithm 
 
result = swapsForMaxSequence(s, p); 
 

 
// Display outcome: 
 
console.log('result:', result); 
 

 
// Second sample: 
 
var s = '1110000111', // Special case 
 
    k = 1, 
 
    p = 3; 
 

 
// Display input: 
 
console.log('s:', s, 'k:', k, 'p:', p); 
 

 
// Run the algorithm 
 
result = swapsForMaxSequence(s, p); 
 

 
// Display outcome: 
 
console.log('result:', result);