Dada una string S no vacía de alfabetos en mayúsculas de longitud L y la tarea es encontrar la string más larga de la string dada con caracteres dispuestos en orden descendente de su código ASCII y en progresión aritmética tal que la diferencia común debe ser tan baja como posible y los caracteres de la string deben tener un valor ASCII más alto.
Nota : la string contiene un mínimo de tres caracteres diferentes.
Ejemplos :
Entrada : S = “ABCPQR”
Salida : “RQP”
Son posibles dos strings de longitud máxima: “CBA” y “RPQ”. Pero dado que
la string debe tener un valor ASCII más alto, la salida es «RPQ».
Entrada : S = “ADGJPRT”
Salida : “JGDA”
Enfoque : la diferencia común máxima posible para que un mínimo de 3 caracteres estén en progresión aritmética es 12. Por lo tanto, calcule previamente todos los caracteres que están presentes en la string utilizando un mapa hash y luego itere desde el carácter que tiene el valor ASCII máximo, es decir, ‘Z’ hasta el carácter. tener un valor ASCII mínimo, es decir, ‘A’. Si el carácter actual existe en la string dada, considérelo como el carácter inicial de la secuencia de progresión aritmética e itere nuevamente sobre todas las diferencias comunes posibles, es decir, del 1 al 12. Verifique para cada diferencia común actual que si el carácter existe en la string dada , incremente la longitud actual de la string requerida más larga. Ahora, existen dos casos en los que es necesario actualizar la longitud máxima y la diferencia común mínima.
- Cuando la longitud actual es mayor que la longitud máxima.
- Cuando la longitud actual es igual a la longitud máxima y la diferencia común actual es menor que la diferencia común mínima, es necesario actualizar la diferencia común.
Además, en cada actualización de estos dos parámetros, también se debe actualizar el carácter inicial de la string o secuencia de progresión aritmética.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the longest string
// with characters arranged in non-decreasing
// order of ASCII and in arithmetic progression
#include <bits/stdc++.h>
using namespace std;
// Function to find the longest String
string findLongestString(string S)
{
// Stores the maximum length of required string
int maxLen = 0;
// Stores the optimal starting character of
// required string or arithmetic progression sequence
int bestStartChar;
// Stores the optimal i.e. minimum common difference
// of required string
int minCommonDifference = INT_MAX;
unordered_map<char, bool> mp;
for (int i = 0; i < S.size(); i++)
mp[S[i]] = true;
// Iterate over the loop in non decreasing order
for (int startChar = 'Z'; startChar > 'A'; startChar--) {
// Process further only if current character
// exists in the given string
if (mp[startChar]) {
// Iterate over all possible common differences
// of AP sequence and update maxLen accordingly
for (int currDiff = 1; currDiff <= 12; currDiff++) {
int currLen = 1;
// Iterate over the characters at any interval
// of current common difference
for (int ch = startChar - currDiff; ch >= 'A';
ch -= currDiff) {
if (mp[ch])
currLen++;
else
break;
}
// Update maxLen and other parameters if the currLen
// is greater than maxLen or if the current
// difference is smaller than minCommonDifference
if (currLen > maxLen || (currLen == maxLen
&& currDiff < minCommonDifference)) {
minCommonDifference = currDiff;
maxLen = currLen;
bestStartChar = startChar;
}
}
}
}
string longestString = "";
// Store the string in decreasing order of
// arithmetic progression
for (int i = bestStartChar;
i >= (bestStartChar - (maxLen - 1) * minCommonDifference);
i -= minCommonDifference)
longestString += char(i);
return longestString;
}
// Driver Code
int main()
{
string S = "ADGJPRT";
cout << findLongestString(S) << endl;
return 0;
}
Java
// Java Program to find the longest string
// with characters arranged in non-decreasing
// order of ASCII and in arithmetic progression
import java.util.*;
import java.lang.*;
public class GFG {
// Function to find the longest String
static String findLongestString(String S)
{
// Stores the maximum length of required string
int maxLen = 0;
// Stores the optimal starting character of
// required string or arithmetic progression sequence
int bestStartChar = 0;
// Stores the optimal i.e. minimum common difference
// of required string
int minCommonDifference = Integer.MAX_VALUE;
HashMap <Character, Boolean> hm = new HashMap
<Character, Boolean>();
for (int i = 0; i < S.length(); i++)
hm.put(S.charAt(i), true);
// Iterate over the loop in non decreasing order
for (int startChar = 'Z'; startChar > 'A'; startChar--) {
// Process further only if current character
// exists in the given string
if (hm.containsKey((char)startChar)) {
// Iterate over all possible common differences
// of AP sequence and update maxLen accordingly
for (int currDiff = 1; currDiff <= 12; currDiff++) {
int currLen = 1;
// Iterate over the characters at any interval
// of current common difference
for (int ch = startChar - currDiff; ch >= 'A';
ch -= currDiff) {
if (hm.containsKey((char)ch))
currLen++;
else
break;
}
// Update maxLen and other parameters if the currLen
// is greater than maxLen or if the current
// difference is smaller than minCommonDifference
if (currLen > maxLen || (currLen == maxLen
&& currDiff < minCommonDifference)) {
minCommonDifference = currDiff;
maxLen = currLen;
bestStartChar = startChar;
}
}
}
}
String longestString = "";
// Store the string in decreasing order of
// arithmetic progression
char ch;
for (int i = bestStartChar;
i >= (bestStartChar - (maxLen - 1) * minCommonDifference);
i -= minCommonDifference)
{
ch = (char)i;
longestString += ch;
}
return longestString;
}
// Driver Code
public static void main(String args[])
{
String S = "ADGJPRT";
System.out.println(findLongestString(S));
}
}
// This code is contributed by Nishant Tanwar
Python3
# Python 3 Program to find the longest string
# with characters arranged in non-decreasing
# order of ASCII and in arithmetic progression
import sys
# Function to find the longest String
def findLongestString(S):
# Stores the maximum length of required string
maxLen = 0
# Stores the optimal starting character of
# required string or arithmetic progression sequence
bestStartChar = 0
# Stores the optimal i.e. minimum common difference
# of required string
minCommonDifference = sys.maxsize
mp = {}
for i in range(len(S)):
mp[S[i]] = True
# Iterate over the loop in non decreasing order
for startChar in range(ord('Z'), ord('A'), -1):
# Process further only if current character
# exists in the given string
if chr(startChar) in mp:
# Iterate over all possible common differences
# of AP sequence and update maxLen accordingly
for currDiff in range(1, 13):
currLen = 1
# Iterate over the characters at any interval
# of current common difference
for ch in range(startChar - currDiff, ord('A') - 1, -currDiff):
if (chr(ch) in mp):
currLen += 1
else:
break
# Update maxLen and other parameters if the currLen
# is greater than maxLen or if the current
# difference is smaller than minCommonDifference
if (currLen > maxLen or (currLen == maxLen
and currDiff < minCommonDifference)):
minCommonDifference = currDiff
maxLen = currLen
bestStartChar = startChar
longestString = ""
# Store the string in decreasing order of
# arithmetic progression
for i in range(bestStartChar,
(bestStartChar - (maxLen - 1) * minCommonDifference)-1, -minCommonDifference):
longestString += chr(i)
return longestString
# Driver Code
if __name__ == "__main__":
S = "ADGJPRT"
print(findLongestString(S))
# This code is contributed by ukasp.
C#
// C# Program to find the longest string
// with characters arranged in non-decreasing
// order of ASCII and in arithmetic progression
using System;
using System.Collections ;
public class GFG {
// Function to find the longest String
static String findLongestString(String S)
{
// Stores the maximum length of required string
int maxLen = 0;
// Stores the optimal starting character of
// required string or arithmetic progression sequence
int bestStartChar = 0;
// Stores the optimal i.e. minimum common difference
// of required string
int minCommonDifference = Int32.MaxValue ;
Hashtable hm = new Hashtable ();
for (int i = 0; i < S.Length; i++)
hm.Add(S[i], true);
// Iterate over the loop in non decreasing order
for (int startChar = 'Z'; startChar > 'A'; startChar--) {
// Process further only if current character
// exists in the given string
if (hm.ContainsKey((char)startChar)) {
// Iterate over all possible common differences
// of AP sequence and update maxLen accordingly
for (int currDiff = 1; currDiff <= 12; currDiff++) {
int currLen = 1;
// Iterate over the characters at any interval
// of current common difference
for (int ch = startChar - currDiff; ch >= 'A';
ch -= currDiff) {
if (hm.ContainsKey((char)ch))
currLen++;
else
break;
}
// Update maxLen and other parameters if the currLen
// is greater than maxLen or if the current
// difference is smaller than minCommonDifference
if (currLen > maxLen || (currLen == maxLen
&& currDiff < minCommonDifference)) {
minCommonDifference = currDiff;
maxLen = currLen;
bestStartChar = startChar;
}
}
}
}
String longestString = "";
// Store the string in decreasing order of
// arithmetic progression
char ch1;
for (int i = bestStartChar;
i >= (bestStartChar - (maxLen - 1) * minCommonDifference);
i -= minCommonDifference)
{
ch1 = (char)i;
longestString += ch1;
}
return longestString;
}
// Driver Code
public static void Main()
{
String S = "ADGJPRT";
Console.WriteLine(findLongestString(S));
}
// This code is contributed by Ryuga
}
Producción:
JGDA
Complejidad de tiempo : O(|S| + 26*12*26), donde |S| es el tamaño de la string.
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA