[プログラマ]文字列の圧縮

Problem

問題の説明
データ処理の専門家になりたいarfitchは、文字列を圧縮する方法を学んでいます.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.
例えば、aabacccについては、2 a 2 ba 3 c(文字が重複せず、一度しか出現せず、1を省略する)と表すことができ、この方法の欠点は、重複文字が少ない場合に圧縮率が低いことである.たとえばabcabcdedeのような文字列は圧縮されません.この欠点を解決するために、ピッチは、文字列を1つ以上の単位に切り取って圧縮し、より短い文字列として表す方法を探します.
例えば、abbcdcababcdcdの場合、文字を1単位に切り取ると全く圧縮されないが、2単位に切り取ると2 ab 2 cdとして表すことができる.異なる方法で8単位でせん断と圧縮を行う場合は、2 abbcdcdを用いて表すことができ、この場合圧縮が最も短い.
別の例はabcabcdedeであり、文字を2単位に切り取って圧縮するとabcabc 2 deであり、3単位に切り取ると2 abcdedeであり、この3単位が最も短い圧縮方法である.3つの単位を切り取り、最後に残った文字列を貼り付けます.
圧縮する文字列sをパラメータとして指定する場合は、上述した方法に従って1つ以上の単位で文字列を切り取り、solution関数を完了して、表す文字列の中で最も短い長さを返します.
せいげんじょうけん
sの長さは1または1000以下である.
sは小文字のみからなる.
I/O例
s result
"aabbaccc" 7
"ababcdcdababcdcd" 9
"abcabcdede" 8
"abcabcabcabcdededededede" 14
"xababcdcdababcdcd" 17
I/O例説明
I/O例#1
文字列を1つの単位で切り取って圧縮する場合に最も短い.
I/O例#2
文字列を8単位で切り取って圧縮する場合が最も短い.
I/O例#3
文字列を3つの単位で切り取って圧縮する場合に最も短い.
I/O例#4
文字列を2つの単位で切断すると、その文字列はabcabcabc 6 deになります.
文字列を3単位に切り取ると、4 abcdededededededeedが生成されます.
文字列を4単位に切り取るとabcabcabc 3 dedeが生成されます.
文字列を6単位で切断すると、2 abcabc 2 dedeとなり、長さは最短14となる.
I/O例#5
文字列は、先頭から指定した長さで切り捨てなければなりません.
したがって、所与の文字列をx/abbcdcd/abbcdcdに切り取ることはできない.
この場合、最も短い長さは17であり、どうしても文字列を切り取っても圧縮されないためである.

Code

function solution(s) {
    var answer = Number.MAX_SAFE_INTEGER;
    const len = s.length;
    
    if (len < 2) return 1;
    
    // 문자열 길이 반절만큼만, 길이
    for (let i = 1; i <= len/2; i++) 
    {
        // 길이 i인 시작 문자열
        let temp = s.substr(0, i);
        // 문자열 반복 횟수
        let count = 1;
        // 압축된 문자열 저장
        let str = "";

        // 길이 i인 반복문자열 찾기
        // 자바스크립트는 인덱스 초과했을 경우 "" 빈문자열 리턴 따라서 "=" 사용
        // 그래서 길이 2, length of str = 6 일 때 p=6까지 비교할 수 있음
        for (let p = i; p <= len; p = p + i)
        {
            // 길이 i인 다음 문자열
            // 인덱스 p 부터 길이 i 문자열 추출
            const next = s.substr(p, i)
            
            // 문자열이 같으면 반복횟수 증가 
            if (temp == next) count++;
            else 
            {
              	// tr에 압축된 문자열 저장
                str += count > 1 ? `${count}${temp}`: temp; 
                temp = next; // 비교 문자열 변경
                count = 1; // 반복횟수 초기화
            }
            
            // 반복되는 문자열 길이보다 나머지 문자열이 작은 경우 처리
            // 여기에 남아있는 문자열은 길이 i 보다 작은 문자열 반족 가능성x
            if (p + i > len) str += temp;
        }
        // 길이 i인 문자열 압축 후 결과물이 기존 압축문자열 길이보다 작을 때 변경
        if (answer > str.length) answer = str.length;

    }
    
    return answer;
}

時間的複雑さ=O(n^2)、MxKなので
Space complexity= O(??) ?? これはあまり...文字列はずっと生成されていますが、スペースが消費されていますか?