Dada la string str de alfabetos en minúsculas, la tarea es encontrar la longitud de la substring más larga de caracteres en orden alfabético, es decir, la string «df abc k» devolverá 3. Tenga en cuenta que el orden alfabético aquí se considera circular, es decir , a, b, c, d, e, …, x, y, z, a, b, c, … .
Ejemplos:
Entrada: str = “abcabcdefabc”
Salida: 6
Todas las substrings válidas son “abc”, “abcdef” y “abc”
Y la longitud de la más larga es 6Entrada: str = “zabcd”
Salida: 5
Acercarse:
- Inicialice i = 0 y len = 0 y, a partir de i, encuentre el índice final de la substring válida más larga y lo almacene, al final .
- Ahora, actualice len = max(end – i + 1, len) e i = end + 1 (para obtener la siguiente substring válida a partir del índice end + 1 ) y repita el paso 1 hasta que i < len(str) .
- Imprime el valor de len al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the ending index for the
// largest valid sub-string starting from index i
int getEndingIndex(string str, int n, int i)
{
i++;
while (i < n)
{
char curr = str[i];
char prev = str[i-1];
// If the current character appears after
// the previous character according to
// the given circular alphabetical order
if ((curr == 'a' && prev == 'z') ||
(curr - prev == 1))
i++;
else
break;
}
return i - 1;
}
// Function to return the length of the longest
// sub-string of consecutive characters from str
int largestSubStr(string str, int n)
{
int len = 0;
int i = 0;
while (i < n)
{
// Valid sub-string exists from index
// i to end
int end = getEndingIndex(str, n, i);
// Update the length
len = max(end - i + 1, len);
i = end + 1;
}
return len;
}
// Driver code
int main()
{
string str = "abcabcdefabc";
int n = str.length();
cout << (largestSubStr(str, n));
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
class GFG {
// Function to return the ending index for the
// largest valid sub-string starting from index i
static int getEndingIndex(String str, int n, int i)
{
i++;
while (i < n) {
char curr = str.charAt(i);
char prev = str.charAt(i - 1);
// If the current character appears after
// the previous character according to
// the given circular alphabetical order
if ((curr == 'a' && prev == 'z') ||
(curr - prev == 1))
i++;
else
break;
}
return i - 1;
}
// Function to return the length of the longest
// sub-string of consecutive characters from str
static int largestSubStr(String str, int n)
{
int len = 0;
int i = 0;
while (i < n) {
// Valid sub-string exists from index
// i to end
int end = getEndingIndex(str, n, i);
// Update the length
len = Math.max(end - i + 1, len);
i = end + 1;
}
return len;
}
// Driver code
public static void main(String args[])
{
String str = "abcabcdefabc";
int n = str.length();
System.out.print(largestSubStr(str, n));
}
}
Python3
# Python3 implementation of the approach # Function to return the ending index for the # largest valid sub-string starting from index i def getEndingIndex(str1, n, i): i += 1 while (i < n): curr = str1[i] prev = str1[i - 1] # If the current character appears after # the previous character according to # the given circular alphabetical order if ((curr == 'a' and prev == 'z') or (ord(curr) - ord(prev) == 1)): i += 1 else: break return i - 1 # Function to return the length of the # longest sub-string of consecutive # characters from str1 def largestSubstr1(str1, n): Len = 0 i = 0 while (i < n): # Valid sub-string exists from # index i to end end = getEndingIndex(str1, n, i) # Update the Length Len = max(end - i + 1, Len) i = end + 1 return Len # Driver code str1 = "abcabcdefabc" n = len(str1) print(largestSubstr1(str1, n)) # This code is contributed by # Mohit Kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the ending index for the
// largest valid sub-string starting from index i
static int getEndingIndex(string str, int n, int i)
{
i++;
while (i < n)
{
char curr = str[i];
char prev = str[i - 1];
// If the current character appears after
// the previous character according to
// the given circular alphabetical order
if ((curr == 'a' && prev == 'z') ||
(curr - prev == 1))
i++;
else
break;
}
return i - 1;
}
// Function to return the length of the longest
// sub-string of consecutive characters from str
static int largestSubStr(string str, int n)
{
int len = 0;
int i = 0;
while (i < n)
{
// Valid sub-string exists from index
// i to end
int end = getEndingIndex(str, n, i);
// Update the length
len = Math.Max(end - i + 1, len);
i = end + 1;
}
return len;
}
// Driver code
public static void Main()
{
string str = "abcabcdefabc";
int n = str.Length;
Console.Write(largestSubStr(str, n));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to return the ending index
// for the largest valid sub-string
/// starting from index i
function getEndingIndex($str, $n, $i)
{
$i++;
while ($i < $n)
{
$curr = $str[$i];
$prev = $str[$i - 1];
// If the current character appears after
// the previous character according to
// the given circular alphabetical order
if (($curr == 'a' && $prev == 'z') ||
(ord($curr) - ord($prev) == 1))
$i++;
else
break;
}
return $i - 1;
}
// Function to return the length of the longest
// sub-string of consecutive characters from str
function largestSubStr($str, $n)
{
$len = 0;
$i = 0;
while ($i < $n)
{
// Valid sub-string exists from index
// i to end
$end = getEndingIndex($str, $n, $i);
// Update the length
$len = max($end - $i + 1, $len);
$i = $end + 1;
}
return $len;
}
// Driver code
$str = "abcabcdefabc";
$n = strlen($str);
echo largestSubStr($str, $n);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the ending index for the
// largest valid sub-string starting from index i
function getEndingIndex(str,n,i)
{
i++;
while (i < n) {
let curr = str[i];
let prev = str[i - 1];
// If the current character appears after
// the previous character according to
// the given circular alphabetical order
if ((curr == 'a' && prev == 'z') ||
(curr.charCodeAt(0) - prev.charCodeAt(0) == 1))
i++;
else
break;
}
return i - 1;
}
// Function to return the length of the longest
// sub-string of consecutive characters from str
function largestSubStr(str,n)
{
let len = 0;
let i = 0;
while (i < n) {
// Valid sub-string exists from index
// i to end
let end = getEndingIndex(str, n, i);
// Update the length
len = Math.max(end - i + 1, len);
i = end + 1;
}
return len;
}
// Driver code
let str = "abcabcdefabc";
let n = str.length;
document.write(largestSubStr(str, n));
// This code is contributed by patel2127
</script>
Producción:
6
Complejidad de tiempo: O(n) donde n es la longitud de la string de entrada. Tenga en cuenta que aumentamos el índice al final.