算法设计：由元音和辅音交替组成的最长的子序列

2021年4月1日18:17:24 发表评论 1,016 次浏览

本文概述

给定一个非空字符串S，任务是打印字符串S中包含交替元音和辅音的最长子序列。

注意：如果存在多个具有相同长度的子序列, 请打印其字符的ASCII值最大的子序列。

例子：

输入：S ="geeksforgeeks"
输出：gesores
解释：" gekorek", " gekores", " gekogek", " gekoges", " gesorek", " gesores", " gesogek", " gesoges", " geforek", " gefores" ", " gefogek"和" gefoges"是可能的最长子序列, 辅音和元音交替出现。 " gesores"是具有最大ASCII字符值之和的子序列, 因此是解决方案。
输入：S =" ababababab"
输出：ababababab
说明：" ababababab"是最长的子序列, 包含交替的元音和辅音。

方法：

请按照以下步骤解决问题：

  • 存储的第一个字符的ASCII值小号作为当前块的最大值(马克西)和中的字符类型旗。如果字符是辅音, 则设置旗as0和1除此以外。
  • 遍历字符串的其余部分。
  • 对于每个字符, 检查它是否与前一个字符属于同一块。
  • 如果属于同一区块, 请更新马克西到max(maxi, i的ASCII值th字符)。
  • 否则, 请在字符后附加ASCII值马克西答案。存储当前i的ASCII值th字符为马克西。更新资料旗to(标志+1)％2表示当前字符的类型。
  • 遍历整个字符串后, 请添加具有ASCII值的字符马克西答案。打印代表子序列的最后一个字符串。

下面的代码是上述方法的实现：

C ++

// C++ program to find the longest
// subsequence containing alternating
// vowels and consonants
#include <bits/stdc++.h>
using namespace std;
 
// Function that return 1 or 0
// if the given character is
// vowel or consonant respectively
int isVowel( char c)
{
     
     // Returns 1 if c is vowel
     if (c == 'a' || c == 'e' ||
         c == 'i' || c == 'o' ||
         c == 'u' )
         return 1;
 
     // Returns 0 if
     // c is consonant
     return 0;
}
 
// Function to find the longest
// subsequence containing
// alternate vowels and
// consonants
string Subsequence(string str)
{
     
     // Store the length
     // of the string
     int n = str.length();
 
     // Assume first character
     // to be consonant
     int flag = 0;
     
     // If first character is vowel
     if (isVowel(str[0]) == 1)
         flag = 1;
         
     // Store the ASCII value
     int maxi = ( int )str[0];
     
     // Stores the final answer
     string ans = "" ;
     for ( int i = 1; i < n; i++)
     {
         
         // If the current character belongs
         // to same category (Vowel / Consonant)
         // as the previous character
         if (isVowel(str[i]) == flag)
         {
             
             // Store the maximum ASCII value
             maxi = max(maxi, ( int )str[i]);
         }
         
         // Otherwise
         else
         {
             
             // Store the character with
             // maximum ASCII value from
             // the previous block
             ans += ( char )(maxi);
             
             // Store the ASCII of the
             // current character as the
             // maximum of the current block
             maxi = ( int )str[i];
             
             // Switch the type of the
             // current block
             flag = (flag + 1) % 2;
         }
     }
     
     // Store the chracter with
     // maximum ASCII value
     // from the last block
     ans += ( char )(maxi);
 
     // Return the result
     return ans;
}
 
// Driver code
int main()
{
     string str = "geeksforgeeks" ;
     
     cout << (Subsequence(str));
}
 
// This code is contributed by chitranayal

Java

// Java program to find the longest
// subsequence containing alternating
// vowels and consonants
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
class GFG {
 
     // Function that return 1 or 0
     // if the given character is
     // vowel or consonant respectively
     static int isVowel( char c)
     {
         // Returns 1 if c is vowel
         if (c == 'a' || c == 'e'
             || c == 'i' || c == 'o'
             || c == 'u' )
             return 1 ;
 
         // Returns 0 if
         // c is consonant
         return 0 ;
     }
 
     // Function to find the longest
     // subsequence containing
     // alternate vowels and
     // consonants
     static String Subsequence(String str)
     {
         // Store the length
         // of the string
         int n = str.length();
 
         // Assume first character
         // to be consonant
         int flag = 0 ;
         // If first character is vowel
         if (isVowel(str.charAt( 0 )) == 1 )
             flag = 1 ;
         // Store the ASCII value
         int maxi = ( int )str.charAt( 0 );
         // Stores the final answer
         String ans = "" ;
         for ( int i = 1 ; i < n; i++) {
             // If the current character belongs
             // to same category (Vowel / Consonant)
             // as the previous character
             if (isVowel(str.charAt(i)) == flag) {
                 // Store the maximum ASCII value
                 maxi = Math.max(maxi, ( int )str.charAt(i));
             }
             // Otherwise
             else {
                 // Store the character with
                 // maximum ASCII value from
                 // the previous block
                 ans += ( char )(maxi);
                 // Store the ASCII of the
                 // current character as the
                 // maximum of the current block
                 maxi = ( int )str.charAt(i);
                 // Switch the type of the
                 // current block
                 flag = (flag + 1 ) % 2 ;
             }
         }
         // Store the chracter with
         // maximum ASCII value
         // from the last block
         ans += ( char )(maxi);
 
         // Return the result
         return ans;
     }
 
     // Driver Program
     public static void main(String[] args)
     {
         String str = "geeksforgeeks" ;
         System.out.println(Subsequence(str));
     }
}

Python3

# Python3 program to find the longest
# subsequence containing alternating
# vowels and consonants
 
def isVowel(c):
   
     # boolean function that check whether
     # the given char is vowel or not
     # and returns a boolean value respectively
     vowels = [ 'a' , 'e' , 'i' , 'o' , 'u' ]
     if (c in vowels):
         return True
     return False
def Subsequence( str ):
   
     #string that stores the final result
     ans = ''
     flag = (isVowel( str [ 0 ]))
     
     #taking the first character
     #as the maximum ASCII valued char
     maxi = ord ( str [ 0 ])
     for i in range ( 1 , len ( str )):
       
         # If the current character belongs to
         # same category(Vowel / Consonant) as the
         # previous character
         if (isVowel( str [i]) = = flag):
           
             # choosing a maximum ASCII valued char
             maxi = max (maxi, ord ( str [i]))
             
         #otherwise
         else :
             ans = ans + chr (maxi)
             maxi = ord ( str [i])
             
             #toggling the flag
             flag = not (flag)
             
     #adding the last char to the answer
     ans = ans + chr (maxi)
     return ans
   
#Driver program
if __name__ = = "__main__" :
     input_string = 'geeksforgeeks'
     print (Subsequence(input_string))
     
# Contributed by
# Nvss Maneesh Gupta

C#

// C# program to find the longest
// subsequence containing alternating
// vowels and consonants
using System;
 
class GFG{
 
// Function that return 1 or 0
// if the given character is
// vowel or consonant respectively
static int isVowel( char c)
{
     
     // Returns 1 if c is vowel
     if (c == 'a' || c == 'e' ||
         c == 'i' || c == 'o' ||
         c == 'u' )
         return 1;
 
     // Returns 0 if
     // c is consonant
     return 0;
}
 
// Function to find the longest
// subsequence containing
// alternate vowels and
// consonants
static String Subsequence(String str)
{
     
     // Store the length
     // of the string
     int n = str.Length;
 
     // Assume first character
     // to be consonant
     int flag = 0;
     
     // If first character is vowel
     if (isVowel(str[0]) == 1)
         flag = 1;
     
     // Store the ASCII value
     int maxi = ( int )str[0];
     
     // Stores the readonly answer
     String ans = "" ;
     
     for ( int i = 1; i < n; i++)
     {
         
     // If the current character belongs
     // to same category (Vowel / Consonant)
     // as the previous character
     if (isVowel(str[i]) == flag)
     {
             
         // Store the maximum ASCII value
         maxi = Math.Max(maxi, ( int )str[i]);
     }
         
     // Otherwise
     else
     {
             
         // Store the character with
         // maximum ASCII value from
         // the previous block
         ans += ( char )(maxi);
             
         // Store the ASCII of the
         // current character as the
         // maximum of the current block
         maxi = ( int )str[i];
             
         // Switch the type of the
         // current block
         flag = (flag + 1) % 2;
     }
     }
     
     // Store the chracter with
     // maximum ASCII value
     // from the last block
     ans += ( char )(maxi);
 
     // Return the result
     return ans;
}
 
// Driver code
public static void Main(String[] args)
{
     String str = "geeksforgeeks" ;
     
     Console.WriteLine(Subsequence(str));
}
}
 
// This code is contributed by 29AjayKumar

输出如下

gesores

时间复杂度：O(n)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: