Dada una string, imprime la substring más larga sin repetir caracteres. Por ejemplo, las substrings más largas sin caracteres repetidos para «ABDEFGABEF» son «BDEFGA» y «DEFGAB», con una longitud de 6. Para «BBBB», la substring más larga es «B», con una longitud de 1. La complejidad de tiempo deseada es O(n ) donde n es la longitud de la string.
Requisito previo: Longitud de la substring más larga sin caracteres repetidos
Ejemplos:
Input : GEEKSFORGEEKS Output : EKSFORG Input : ABDEFGABEF Output : BDEFGA
Acercarse:La idea es recorrer la string y almacenar su última aparición en una tabla hash para cada carácter ya visitado (aquí unordered_map se usa como un hash con la clave como carácter y el valor como su última posición). 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, verifique si el carácter actual está presente en la tabla hash o no. Si no está presente, almacene el carácter actual en la tabla hash con valor como índice actual. Si ya está presente en la tabla hash, esto significa que el carácter actual podría repetirse en la substring actual. Para esta verificación, si la ocurrencia 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 tabla hash. Si es posterior a st, busque la longitud de la substring actual que se muestra 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[inicio] a s[inicio+maxlen-1].
Implementación:
C++
// C++ program to find and print longest
// substring without repeating characters.
#include <bits/stdc++.h>
using namespace std;
// Function to find and print longest
// substring without repeating characters.
string findLongestSubstring(string str)
{
int i;
int n = str.length();
// starting point of current substring.
int st = 0;
// length of current substring.
int currlen;
// maximum length substring without repeating
// characters.
int maxlen = 0;
// starting index of maximum length substring.
int start;
// Hash Map to store last occurrence of each
// already visited character.
unordered_map<char, int> pos;
// Last occurrence of first character is index 0;
pos[str[0]] = 0;
for (i = 1; i < n; i++) {
// If this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (pos.find(str[i]) == pos.end())
pos[str[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[str[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[str[i]] + 1;
}
// Update last occurrence of
// current character.
pos[str[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 longest substring without
// repeating characters is from str[start]
// to str[start+maxlen-1].
return str.substr(start, maxlen);
}
// Driver function
int main()
{
string str = "GEEKSFORGEEKS";
cout << findLongestSubstring(str);
return 0;
}
Java
// Java program to find
// and print longest substring
// without repeating characters.
import java.util.*;
class GFG{
// Function to find and print longest
// substring without repeating characters.
public static String findLongestSubstring(String str)
{
int i;
int n = str.length();
// Starting point
// of current substring.
int st = 0;
// length of
// current substring.
int currlen = 0;
// maximum length
// substring without
// repeating characters.
int maxlen = 0;
// starting index of
// maximum length substring.
int start = 0;
// Hash Map to store last
// occurrence of each
// already visited character.
HashMap<Character,
Integer> pos = new HashMap<Character,
Integer>();
// Last occurrence of first
// character is index 0;
pos.put(str.charAt(0), 0);
for (i = 1; i < n; i++)
{
// If this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (!pos.containsKey(str.charAt(i)))
{
pos.put(str.charAt(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.get(str.charAt(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.get(str.charAt(i)) + 1;
}
// Update last occurrence of
// current character.
pos.replace(str.charAt(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 longest
// substring without
// repeating characters
// is from str[start]
// to str[start+maxlen-1].
return str.substring(start,
start +
maxlen);
}
// Driver Code
public static void main(String[] args)
{
String str = "GEEKSFORGEEKS";
System.out.print(findLongestSubstring(str));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to find and print longest
# substring without repeating characters.
# Function to find and print longest
# substring without repeating characters.
def findLongestSubstring(string):
n = len(string)
# starting point of current substring.
st = 0
# maximum length substring without
# repeating characters.
maxlen = 0
# starting index of maximum
# length substring.
start = 0
# Hash Map to store last occurrence
# of each already visited character.
pos = {}
# Last occurrence of first
# character is index 0
pos[string[0]] = 0
for i in range(1, n):
# If this character is not present in hash,
# then this is first occurrence of this
# character, store this in hash.
if string[i] not in pos:
pos[string[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[string[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[string[i]] + 1
# Update last occurrence of
# current character.
pos[string[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 longest substring without
# repeating characters is from string[start]
# to string[start+maxlen-1].
return string[start : start + maxlen]
# Driver Code
if __name__ == "__main__":
string = "GEEKSFORGEEKS"
print(findLongestSubstring(string))
# This code is contributed by Rituraj Jain
C#
// C# program to find
// and print longest substring
// without repeating characters.
using System;
using System.Collections.Generic;
class GFG{
// Function to find and
// print longest substring
// without repeating characters.
public static String findlongestSubstring(String str)
{
int i;
int n = str.Length;
// Starting point
// of current substring.
int st = 0;
// length of
// current substring.
int currlen = 0;
// maximum length
// substring without
// repeating characters.
int maxlen = 0;
// starting index of
// maximum length substring.
int start = 0;
// Hash Map to store last
// occurrence of each
// already visited character.
Dictionary<char,
int> pos = new Dictionary<char,
int>();
// Last occurrence of first
// character is index 0;
pos.Add(str[0], 0);
for (i = 1; i < n; i++)
{
// If this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (!pos.ContainsKey(str[i]))
{
pos.Add(str[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[str[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[str[i]] + 1;
}
// Update last occurrence of
// current character.
pos[str[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 longest
// substring without
// repeating characters
// is from str[start]
// to str[start+maxlen-1].
return str.Substring(start,
maxlen);
}
// Driver Code
public static void Main(String[] args)
{
String str = "GEEKSFORGEEKS";
Console.Write(findlongestSubstring(str));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to find and print longest
// substring without repeating characters.
function findLongestSubstring(str)
{
var i;
var n = str.length;
// starting point of current substring.
var st = 0;
// length of current substring.
var currlen;
// maximum length substring without repeating
// characters.
var maxlen = 0;
// starting index of maximum length substring.
var start;
// Hash Map to store last occurrence of each
// already visited character.
var pos = new Map();
// Last occurrence of first character is index 0;
pos.set(str[0], 0);
for (var i = 1; i < n; i++) {
// If this character is not present in hash,
// then this is first occurrence of this
// character, store this in hash.
if (!pos.has(str[i]))
pos.set(str[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.get(str[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.get(str[i]) + 1;
}
// Update last occurrence of
// current character.
pos.set(str[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 longest substring without
// repeating characters is from str[start]
// to str[start+maxlen-1].
return str.substr(start,maxlen);
}
var str = "GEEKSFORGEEKS";
document.write(findLongestSubstring(str));
// This code is contributed by SoumikMondal
</script>
Producción:
EKSFORG
Complejidad temporal: O(n)
Espacio auxiliar: O(n)