1209. Remove All Adjacent Duplicates in String II

LeetCode medium оригинал: C# #array #csharp #leetcode #medium #stack #string

LeetCode Static

Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.

Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.

Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.

Пример:

Input: s = "deeedbbcccbdaa", k = 3

Output: "aa"

Explanation:

First delete "eee" and "ccc", get "ddbbbdaa"

Then delete "bbb", get "dddaa"

Finally delete "ddd", get "aa"

C# решение

сопоставлено/оригинал

public class Solution {
    public string RemoveDuplicates(string s, int k) {
        Stack<int> counts = new Stack<int>();
        char[] sa = s.ToCharArray();
        int j = 0;
        
        for (int i = 0; i < sa.Length; ++i, ++j) {
            sa[j] = sa[i];
            if (j == 0 || sa[j] != sa[j - 1]) {
                counts.Push(1);
            } else {
                int incremented = counts.Pop() + 1;
                if (incremented == k) {
                    j -= k;
                } else {
                    counts.Push(incremented);
                }
            }
        }
        return new string(sa, 0, j);
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string RemoveDuplicates(string s, int k) {
        stack<int> counts = new stack<int>();
        char[] sa = s.ToCharArray();
        int j = 0;
        
        for (int i = 0; i < sa.size(); ++i, ++j) {
            sa[j] = sa[i];
            if (j == 0 || sa[j] != sa[j - 1]) {
                counts.push(1);
            } else {
                int incremented = counts.pop() + 1;
                if (incremented == k) {
                    j -= k;
                } else {
                    counts.push(incremented);
                }
            }
        }
        return new string(sa, 0, j);
    }
}

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public String RemoveDuplicates(String s, int k) {
        Stack<int> counts = new Stack<int>();
        char[] sa = s.ToCharArray();
        int j = 0;
        
        for (int i = 0; i < sa.length; ++i, ++j) {
            sa[j] = sa[i];
            if (j == 0 || sa[j] != sa[j - 1]) {
                counts.push(1);
            } else {
                int incremented = counts.pop() + 1;
                if (incremented == k) {
                    j -= k;
                } else {
                    counts.push(incremented);
                }
            }
        }
        return new String(sa, 0, j);
    }
}

JavaScript решение

сопоставлено/оригинал

class Solution {
    removeDuplicates(s, k) {
        let counts = [];
        let sa = s.split('');
        let j = 0;
        
        for (let i = 0; i < sa.length; ++i, ++j) {
            sa[j] = sa[i];
            if (j === 0 || sa[j] !== sa[j - 1]) {
                counts.push(1);
            } else {
                let incremented = counts.pop() + 1;
                if (incremented === k) {
                    j -= k;
                } else {
                    counts.push(incremented);
                }
            }
        }
        return sa.slice(0, j).join('');
    }
}

Algorithm

Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.

Перемещать быстрый указатель i по строке s:

Копировать s[i] в s[j].

Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.

Иначе добавить 1 в стек.

Если количество символов равно k, уменьшить j на k и извлечь из стека.

Вернуть первые j символов строки.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.