кратчайшая возможная длина сжатого представления строки

Question

У меня есть это упражнение, которое нужно решить в java, и речь идет о некоторых манипуляциях со строками, для которых я понятия не имею, как их решать. Мне было бы более интересно узнать, какой подход следует использовать для его решения, а не предлагать полное решение для кодирования. Итак, вот оно:

Строки с длинными блоками повторяющихся символов занимают намного меньше места, если хранятся в сжатом представлении. Чтобы получить сжатое представление, мы заменяем каждый сегмент одинаковых символов в строке на количество символов в сегменте, за которым следует символ (например, мы заменяем сегмент "CCCC" на 4 C). Чтобы избежать увеличения размера, мы оставляем однобуквенные сегменты без изменений (сжатое представление «B C» - это та же строка - «B C»). Например, сжатое представление строки «ABBBCCDD CCC» является «A3B2C2D3 C», а сжатое представление строки «AAAAAAAAAAABXXAAAAAAAAAA» - «11AB2X10A». Обратите внимание, что во втором примере, если мы удалим сегмент «BXX» из середины слова, мы получим гораздо более короткое сжатое представление - «21A». Чтобы воспользоваться этим наблюдением, мы решили изменить алгоритм сжатия. Теперь перед сжатием мы удаляем ровно K последовательных букв из входной строки. Мы хотели бы знать кратчайшую сжатую форму, которую мы можем сгенерировать таким образом.

Напишите функцию:

 class Solution { 
    public int solution(String S, int K) { 
 } 
} 

, которая задана строкой S длины N и целым числом K, возвращает кратчайшая возможная длина сжатого представления S после удаления ровно K последовательных символов из S.

Пример:

С учетом S = "AAAAAAAAAAABXXAAAAAAAAAA" и K = 3, функция должна вернуть 3, поскольку после удаления «BXX» из S мы остаемся с «AAAAAAAAAAAAAAAAAAAAA», который сжимается до представления длины 3 - «21A».

Требование:

N is an integer within the range [1...100,000];
K is an integer within the range [0...100,000];
K <= N;
string S consists only of uppercase letters (A-Z)

Answer 1

Вот мое довольно явное решение в C#. Я добавил структуру только для разборчивости. Если вы хотите прочитать более подробное объяснение, я написал небольшую статью http://prochal.com/2020/05/the-shortest-possible-length-of-the-compressed-representation-of-a-string/

У меня недостаточно комментариев, но приведенное выше решение PHP требует некоторого исправления , поскольку он возвращает неверный результат для некоторых наборов, таких как:

• решение ('abcabcabca', 10) -> 10, должно возвращать 3
• решение ('abcabcabca', 9) - > 1, должно вернуть 3
• решение ('aaaaaxxxxaaaaaa', 4) -> 5, должно вернуть 3.

    public static int findCompressedLength(string S, int K)
            {
                if (S.Length < 3)
                    return S.Count();
                else if (K >= S.Count()-1)
                    return S.Count().ToString().Length + 1;

                Dictionary<char, int> charsWithFrequencies = new Dictionary<char, int>();
                var windowStart = 0;
                int longestSequence = 0;
                var repetitions = 0;
                var longestSequenceInstance = new longestSequenceInstance();

                for (var i = 0; i < S.Length; i++)
                {
                    if (charsWithFrequencies.ContainsKey(S[i]))
                        charsWithFrequencies[S[i]]++;
                    else
                        charsWithFrequencies.Add(S[i], 1);

                    repetitions = charsWithFrequencies[S[i]];

                    if (i - windowStart - repetitions + 1 > K)
                    {
                        charsWithFrequencies[S[windowStart]]--;
                        windowStart++;
                    }

                    if (i - windowStart + 1 > longestSequence)
                    {
                        longestSequence = i - windowStart + 1;
                        longestSequenceInstance.EndingIndex = i;
                        longestSequenceInstance.StartingIndex = i - longestSequence + 1;
                        longestSequenceInstance.Letter = S[i];
                        longestSequenceInstance.Occurences = longestSequence;
                    }
                }

                var workingString = new StringBuilder(S);
                var replaced = workingString.Remove(longestSequenceInstance.StartingIndex, longestSequenceInstance.Occurences - 1)
                                            .Insert(longestSequenceInstance.StartingIndex, String.Concat(Enumerable.Repeat(longestSequenceInstance.Letter, longestSequenceInstance.Occurences-1)))
                                            .ToString();

                int occurences = 1;
                char currentChar;
                var strBuilder = new StringBuilder("");

                for (var i = 1; i < replaced.Length; i++)
                {
                    currentChar = replaced[i];

                    if (replaced[i - 1] == replaced[i])
                        occurences++;
                    else
                    {
                        if (occurences > 1)
                            strBuilder.Append(occurences);

                        strBuilder.Append(replaced[i - 1]);

                        occurences = 1;
                    }

                    if (i == replaced.Length - 1)
                    {
                        if (occurences > 1)
                            strBuilder.Append(occurences);

                        strBuilder.Append(currentChar);
                    }
                }

                var stringFinal = strBuilder.ToString();
                return stringFinal.Count();
            }

            }

            public struct longestSequenceInstance
            {
                public char Letter { get; set; }
                public int EndingIndex { get; set; }
                public int StartingIndex { get; set; }
                public int Occurences { get; set; }
            }

Answer 2

Используйте Regex, затем проанализируйте строку, чтобы отфильтровать строку K.

Вот решение PHP, вы можете перенести его на Java:

function solution($S, $K){
  $strlen = function($arg){
      $pattern = '/(.)\1*/';
      preg_match_all($pattern, $arg, $matched);

      foreach($matched[0] as $m){
              if (strlen($m) > 1) $shortArr[]=strlen($m);
              $shortArr[] = substr($m,0,1);
      }

      $str = implode("",$shortArr);
      return strlen($str);
  };

  $finalLength = $strlen($S);
  for($i=0;$i<strlen($S)-$K;$i++){
      if(!preg_match('/^(.)\1*$/', substr($S,$i,$K))){
          $firstPart = substr($S,0,$i);
          $lastPart = substr($S,$i+$K);
          $length = $strlen($firstPart . $lastPart);
          if ($length < $finalLength) $finalLength = $length;
      }
  }

  return $finalLength;
}

Лично я думаю, что вопрос неоднозначен. Например, следует ли удалять $ K только один раз или вы можете удалить несколько раз?