Dada una string, imprime la substring más larga sin repetir caracteres en Golang. Por ejemplo, las substrings más largas sin caracteres repetidos para «ABDEFGABEF» son «BDEFGA».
Ejemplos:
Input : GEEKSFORGEEKS Output : Substring: EKSFORG Length: 7 Input : ABDEFGABEF Output : Substring: BDEFGA Length: 6
La idea es recorrer la string y para cada carácter ya visitado almacenar su última aparición en una array pos de números enteros (actualizaremos los índices de la array en función de los valores ASCII de los caracteres de la string). La variable st almacena el punto de inicio de la substring actual, maxlen almacena la longitud de la substring de longitud máxima y start almacena el índice inicial de la substring de longitud máxima.
Mientras recorre la string, compruebe si el carácter actual ya está presente en la string comprobando la array pos . Si no está presente, almacene el índice del carácter actual en la array con el valor como índice actual. Si ya está presente en la array, esto significa que el carácter actual podría repetirse en la substring actual. Para ello, compruebe si la aparición anterior del carácter está antes o después del punto de inicio st de la substring actual. Si está antes de st , solo actualice el valor en la array. Si es posterior a st, entonces busque la longitud de la substring actual currlen como i-st , donde i es el índice actual.
Comparar currlen con maxlen . Si maxlen es menor que currlen, actualice maxlen como currlen y comience como st. Después de completar el recorrido de la string, la substring más larga requerida sin caracteres repetidos es de s[start] a s[start+maxlen-1] .
// Golang program to find the length of the
// longest substring without repeating
// characters
package main
import "fmt"
func longest_substring(s string, n int) string {
var i int
// starting point of
// current substring.
st := 0
// length of current substring.
currlen := 0
// maximum length substring
// without repeating characters
maxlen := 0
// starting index of
// maximum length substring.
start := 0
// this array works as the hash table
// -1 indicates that element is not
// present before else any value
// indicates its previous index
pos := make([]int, 125)
for i = 0; i < 125; i++ {
pos[i] = -1
}
// storing the index
// of first character
pos[s[0]] = 0
for i = 1; i < n; i++ {
// If this character is not present in array,
// then this is first occurrence of this
// character, store this in array.
if pos[s[i]] == -1 {
pos[s[i]] = i
} else {
// If this character is present in hash then
// this character has previous occurrence,
// check if that occurrence is before or after
// starting point of current substring.
if pos[s[i]] >= st {
// find length of current substring and
// update maxlen and start accordingly.
currlen = i - st
if maxlen < currlen {
maxlen = currlen
start = st
}
// Next substring will start after the last
// occurrence of current character to avoid
// its repetition.
st = pos[s[i]] + 1
}
// Update last occurrence of
// current character.
pos[s[i]] = i
}
}
// Compare length of last substring
// with maxlen and update maxlen
// and start accordingly.
if maxlen < i-st {
maxlen = i - st
start = st
}
// the required string
ans := ""
// extracting the string from
// [start] to [start+maxlen]
for i = start; i < start+maxlen; i++ {
ans += string(s[i])
}
return ans
}
func main() {
var s string = "GEEKSFORGEEKS"
var n int = len(s)
// calling the function to
// get the required answer.
var newString = longest_substring(s, n)
// finding the length of the string
var length int = len(newString)
fmt.Println("Longest substring is: ", newString)
fmt.Println("Length of the string: ", length)
}
Producción:
Longest substring is: EKSFORG Length of the string: 7
Nota: en lugar de usar la array, también podemos usar un mapa de string para int .
Publicación traducida automáticamente
Artículo escrito por ManishKhetan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA