Кодирование длины цикла с использованием пространства O (1)

Решение C++ O(n) время O(1) пространство

string runLengthEncode(string str)
{
    int len = str.length();
    int j=0,k=0,cnt=0;
    for(int i=0;i<len;i++)
    {
        j=i;
        cnt=1;
        while(i<len-1 && str[i]==str[i+1])
        {
            i++;
            cnt++;
        }
        str[k++]=str[j];
        string temp =to_string(cnt);
        for(auto m:temp)
            str[k++] = m;
    }
    str.resize(k);
    return str;
}

Моей первой мыслью было начать кодирование с конца, поэтому мы будем использовать свободное место (если оно есть), после этого мы можем сместить кодируемый массив в начало. Проблема с этим подходом в том, что он не будет работать для AAAAB, потому что нет свободного места (для A4B1 оно не нужно) и мы попытаемся написать AAAAB1 на первой итерации.

Ниже приведено исправленное решение: (допустим, последовательность AAABBC)

1. закодировать все группы с двумя или более элементами и оставить остальные без изменений (это не увеличит длину массива) -> A3_B2C
2. сдвиньте все правильно, убрав пустые места после первого шага -> _A3B2C
3. кодировать массив с самого начала (конечно, повторно используя уже закодированные группы) -> A3B2C1

Каждый шаг - это O(n), и, насколько я понимаю, нужна только постоянная дополнительная память.

Ограничения:

1. Цифры не поддерживаются, но это в любом случае создаст проблемы с декодированием, как упомянул Петр Петров.
2. Нужен какой-то "пустой" символ, но это можно обойти добавлением нулей: A03 вместо A3_

null используется для указания того, какие элементы пусты и будут игнорироваться при кодировании. Также вы не можете кодировать цифры (AAA2222 => A324 => 324 раза «A», но это A3; 24). Ваш вопрос открывает больше вопросов.

Вот "решение" на С#

public static void Encode(string[] input)
{
    var writeIndex = 0;

    var i = 0;
    while (i < input.Length)
    {
        var symbol = input[i];
        if (symbol == null)
        {
            break;
        }

        var nextIndex = i + 1;

        var offset = 0;
        var count = CountSymbol(input, symbol, nextIndex) + 1;
        if (count == 1)
        {
            ShiftRight(input, nextIndex);
            offset++;
        }

        input[writeIndex++] = symbol;
        input[writeIndex++] = count.ToString();

        i += count + offset;
    }

    Array.Clear(input, writeIndex, input.Length - writeIndex);
}

private static void ShiftRight(string[] input, int nextIndex)
{
    var count = CountSymbol(input, null, nextIndex, (a, b) => a != b);
    Array.Copy(input, nextIndex, input, nextIndex + 1, count);
}

private static int CountSymbol(string[] input, string symbol, int nextIndex)
{
    return CountSymbol(input, symbol, nextIndex, (a, b) => a == b);
}

private static int CountSymbol(string[] input, string symbol, int nextIndex, Func<string, string, bool> cmp)
{
    var count = 0;

    var i = nextIndex;
    while (i < input.Length && cmp(input[i], symbol))
    {
        count++;
        i++;
    }

    return count;
}

Первое решение не заботится об отдельных символах. Например - "Привет!" не будет работать. Я использовал совершенно другой подход, использовал функции «insert()» для добавления на место. Это позаботится обо всем, будь то общий «один и тот же» символ> 10 или> 100 или = 1.

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
    string name = "Hello Buddy!!";
    int start = 0;
    char distinct = name[0];
    for(int i=1;i<name.length()+1;){
        if(distinct!=name[i]){
            string s = to_string(i-start);
            name.insert(start+1,s);
            name.erase(name.begin() + start + 1 + s.length(),name.begin() + s.length() + i);
            i=start+s.length()+1;
            start=i;
            distinct=name[start];
            continue;
        }
        i++;
    }
    cout<<name;
}

Предложите мне, если вы найдете что-то неправильное.

O(n), RLE на месте, я не мог придумать ничего лучше этого. Он не будет размещать число, если количество символов равно 1. Также будет размещать a9a2, если символ встречается 11 раз.

void RLE(char *str) {
int len = strlen(str);
int count = 1, j = 0;
for (int i = 0; i < len; i++){
    if (str[i] == str[i + 1])
        count++;
    else {
        int times = count / 9;
        int rem = count % 9;
        for (int k = 0; k < times; k++) {
            str[j++] = str[i];
            _itoa(9, &str[j++], 10);
            count = count - 9;
        }
        if (count > 1) {
            str[j++] = str[i];
            _itoa(rem, &str[j++], 10);
            count = 1;
        }
        else 
            str[j++] = str[i];
    }
}
cout << str;

}

I/P => aaabcdeeeefghijklaaaaa

О/П => a3bcde4fghijkla5