[못품/릿코드/javascript] 424

var characterReplacement = function(s, k) {
  //k번만 교환가능하다.(다른 uppercase로.. 즉 k번까지는 제외하고, 가장 길게 연속되어있는 문자열을 구하면 됨.!)
  //가장 긴 연속된 것들을 구해라.
  // A A B A B B A 
  //left는 obj[left] = > 연속된 글자.
  //이제 근데 k개는 교환할 수 있으니까 k개는 있다치고 넘어감.
  //즉 obj[left] => s[left]===s[right]일때 늘어나고, 아닐때도 k개까지는 늘어남.
  //더이상 늘어날 수 없다면(k개 목숨 다썼다면) left++ 해줌.
  //그 다음 obj[left]를 구함. right은 left+1로 바뀜. 그리고 obj중에 제일 큰 숫자 반납하면 됨.
  let obj = {};
  let count = 0;
  let left=0,right=0;
  while(left<s.length){
      if(!obj[left]) obj[left] = 0;
      obj[left]++;
      right++
      if(s[left]!==s[right]) count++;
      if(count>k||right>=s.length) {
          left++
          right = left
          count=0
      }
  }
  let max = 0;
  for(let key in obj){
      max = Math.max(max,obj[key])
  }
  return max
};

내가 처음 풀었던 코드.

left와 right을 이용해서 그 사이의 길이를 측정했다 k번까지는 달라도 그냥 넘어갔음

근데 이렇게 풀면 ABBB의 답이 3이 나오는 불상사가 발생한다.

 

const characterReplacement = (s, k) => {
    let left = 0;
    let right = 0;
    let maxCharCount = 0;
    const visited = {}
    while(right<s.length){
        let char = s[right];
        visited[char] = visited[char] ? visited[char] + 1 : 1;
        if(visited[char]>maxCharCount) maxCharCount = visited[char]
        if(right-left+1-maxCharCount>k){
            visited[s[left]]--;
            left++;
        }
        right++;
    }
    return right-left
};

다른 사람의 풀이

나와의 차이점은 

1. 나는 인덱스로 객체에 저장했지만 알파벳으로 객체에 저장하였다.

2. A===B일경우에 객체에 저장하는게 아니라 right은 일단 카운트하고, 제일 많이나온 알파벳을 maxCharCount에 저장한다.

 -> 이렇게 하면 ABBB같은경우에도 대응이 가능!

3.객체나 maxCharCount를 반환하는 것이 아니라 windowSize를 반환하였다.

right-left+1-maxCharCount 라는 것은 right과 left사이에 교환해야할 것이 k보다 큰가? 하는 물음이다. 그럴경우에 left를 줄여줘서 사이즈를 줄여준다.