GOLANG_INTERVIEW Telegram 1026
👣 Задача: 395. Самая длинная подстрока, содержащая не менее K повторяющихся символов

В этой задаче Вам необходимо найти самую длинную подстроку строки \(s\), такую что каждая буква в ней встречается не менее \(k\) раз.

Если такой подстроки нет, вернуть 0.

Пример:

Вход: s = "aaabb", k = 3
Выход: 3

Объяснение: Самая длинная подходящая подстрока – "aaa", так как буква 'a' повторяется три раза.
### Описание алгоритма:

1. Генерация подстрок: Генерируем все возможные подстроки строки \(s\). Для каждой подстроки будем отслеживать частоту появления символов при помощи массива countMap.

2. Проверка валидности: Метод isValid проверяет, что каждый символ в текущей подстроке появляется хотя бы \(k\) раз. Это делается через проверку значений в массиве countMap. Если все символы удовлетворяют условию, то подстрока считается допустимой.

3. Обновление результата: Отслеживаем максимальную длину допустимых подстрок. Когда находим новую подходящую подстроку большей длины, обновляем результат. В итоге возвращаем длину самой длинной найденной подстроки.
Ответ:



package main

import (
"fmt"
)

func longestSubstring(s string, k int) int {
if len(s) == 0 || k > len(s) {
return 0
}
n := len(s)
result := 0

for start := 0; start < n; start++ {
countMap := make([]int, 26)
for end := start; end < n; end++ {
countMap[s[end]-'a']++
if isValid(countMap, k) {
if end-start+1 > result {
result = end - start + 1
}
}
}
}
return result
}
func isValid(countMap []int, k int) bool {
countLetters, countAtLeastK := 0, 0
for _, count := range countMap {
if count > 0 {
countLetters++
}
if count >= k {
countAtLeastK++
}
}
return countLetters == countAtLeastK
}

func main() {
fmt.Println(longestSubstring("aaabb", 3)) // Output: 3
fmt.Println(longestSubstring("ababbc", 2)) // Output: 5
}


@golang_interview
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥7👍42🥱2🥴2🤣1



tgoop.com/golang_interview/1026
Create:
Last Update:

👣 Задача: 395. Самая длинная подстрока, содержащая не менее K повторяющихся символов

В этой задаче Вам необходимо найти самую длинную подстроку строки \(s\), такую что каждая буква в ней встречается не менее \(k\) раз.

Если такой подстроки нет, вернуть 0.

Пример:


Вход: s = "aaabb", k = 3
Выход: 3

Объяснение: Самая длинная подходящая подстрока – "aaa", так как буква 'a' повторяется три раза.
### Описание алгоритма:

1. Генерация подстрок: Генерируем все возможные подстроки строки \(s\). Для каждой подстроки будем отслеживать частоту появления символов при помощи массива countMap.

2. Проверка валидности: Метод isValid проверяет, что каждый символ в текущей подстроке появляется хотя бы \(k\) раз. Это делается через проверку значений в массиве countMap. Если все символы удовлетворяют условию, то подстрока считается допустимой.

3. Обновление результата: Отслеживаем максимальную длину допустимых подстрок. Когда находим новую подходящую подстроку большей длины, обновляем результат. В итоге возвращаем длину самой длинной найденной подстроки.
Ответ:



package main

import (
"fmt"
)

func longestSubstring(s string, k int) int {
if len(s) == 0 || k > len(s) {
return 0
}
n := len(s)
result := 0

for start := 0; start < n; start++ {
countMap := make([]int, 26)
for end := start; end < n; end++ {
countMap[s[end]-'a']++
if isValid(countMap, k) {
if end-start+1 > result {
result = end - start + 1
}
}
}
}
return result
}
func isValid(countMap []int, k int) bool {
countLetters, countAtLeastK := 0, 0
for _, count := range countMap {
if count > 0 {
countLetters++
}
if count >= k {
countAtLeastK++
}
}
return countLetters == countAtLeastK
}

func main() {
fmt.Println(longestSubstring("aaabb", 3)) // Output: 3
fmt.Println(longestSubstring("ababbc", 2)) // Output: 5
}


@golang_interview

BY Golang вопросы собеседований


Share with your friend now:
tgoop.com/golang_interview/1026

View MORE
Open in Telegram


Telegram News

Date: |

The creator of the channel becomes its administrator by default. If you need help managing your channel, you can add more administrators from your subscriber base. You can provide each admin with limited or full rights to manage the channel. For example, you can allow an administrator to publish and edit content while withholding the right to add new subscribers. According to media reports, the privacy watchdog was considering “blacklisting” some online platforms that have repeatedly posted doxxing information, with sources saying most messages were shared on Telegram. Ng, who had pleaded not guilty to all charges, had been detained for more than 20 months. His channel was said to have contained around 120 messages and photos that incited others to vandalise pro-government shops and commit criminal damage targeting police stations. Those being doxxed include outgoing Chief Executive Carrie Lam Cheng Yuet-ngor, Chung and police assistant commissioner Joe Chan Tung, who heads police's cyber security and technology crime bureau. Telegram offers a powerful toolset that allows businesses to create and manage channels, groups, and bots to broadcast messages, engage in conversations, and offer reliable customer support via bots.
from us


Telegram Golang вопросы собеседований
FROM American