DMS游戏活动中心 - 热门活动与福利速递

给定一个字符串 。任务是找到字符串的字典序最大的子序列，它是一个回文。示例：

Input : str = "abrakadabra"

Output : rr

Input : str = "geeksforgeeks"

Output : ss

这个想法是如果字符 a 的 ASCII 值大于 b 的值，则认为字符 a 在字典上大于字符 b。由于字符串必须是回文，字符串应该只包含最大的字符，就好像我们在第一个和最后一个字符之间放置任何其他较小的字符，那么它会使字符串在字典上更小。要找到字典上最大的子序列，首先找到给定字符串中的最大字符，并将其所有出现在原始字符串中，以形成结果子序列字符串。以下是上述方法的实现：

C++ 实现

// CPP program to find the largest

// palindromic subsequence

#include

using namespace std;

// Function to find the largest

// palindromic subsequence

string largestPalinSub(string s)

{

string res;

char mx = s[0];

// Find the largest character

for (int i = 1; i < s.length(); i++)

mx = max(mx, s[i]);

// Append all occurrences of largest character

// to the resultant string

for (int i = 0; i < s.length(); i++)

if (s[i] == mx)

res += s[i];

return res;

}

// Driver Code

int main()

{

string s = "geeksforgeeks";

cout << largestPalinSub(s);

}

Java实现

// Java program to find the largest

// palindromic subsequence

class GFG

{

// Function to find the largest

// palindromic subsequence

static String largestPalinSub(String s)

{

String res = "";

char mx = s.charAt(0);

// Find the largest character

for (int i = 1; i < s.length(); i++)

mx = (char)Math.max((int)mx,

(int)s.charAt(i));

// Append all occurrences of largest

// character to the resultant string

for (int i = 0; i < s.length(); i++)

if (s.charAt(i) == mx)

res += s.charAt(i);

return res;

}

// Driver Code

public static void main(String []args)

{

String s = "geeksforgeeks";

System.out.println(largestPalinSub(s));

}

}

// This code is contributed by

// Rituraj Jain

Python3实现

# Python3 program to find the largest

# palindromic subsequence

# Function to find the largest

# palindromic subsequence

def largestPalinSub(s):

res = ""

mx = s[0]

# Find the largest character

for i in range(1, len(s)):

mx = max(mx, s[i])

# Append all occurrences of largest

# character to the resultant string

for i in range(0, len(s)):

if s[i] == mx:

res += s[i]

return res

# Driver Code

if __name__ == "__main__":

s = "geeksforgeeks"

print(largestPalinSub(s))

# This code is contributed by

# Rituraj Jain

C#实现

// C# program to find the largest

// palindromic subsequence

using System;

class GFG

{

// Function to find the largest

// palindromic subsequence

static string largestPalinSub(string s)

{

string res = "";

char mx = s[0];

// Find the largest character

for (int i = 1; i < s.Length; i++)

mx = (char)Math.Max((int)mx,

(int)s[i]);

// Append all occurrences of largest

// character to the resultant string

for (int i = 0; i < s.Length; i++)

if (s[i] == mx)

res += s[i];

return res;

}

// Driver Code

public static void Main()

{

string s = "geeksforgeeks";

Console.WriteLine(largestPalinSub(s));

}

}

// This code is contributed by Ryuga

PHP实现

// PHP program to find the largest

// palindromic subsequence

// Function to find the largest

// palindromic subsequence

function largestPalinSub($s)

{

$res="";

$mx = $s[0];

// Find the largest character

for ($i = 1; $i < strlen($s); $i++)

{

$mx = max($mx, $s[$i]);

}

// Append all occurrences of largest character

// to the resultant string

for ($i = 0; $i < strlen($s); $i++)

{

if ($s[$i] == $mx)

{

$res.=$s[$i];

}

}

return $res;

}

// Driver Code

$s = "geeksforgeeks";

echo(largestPalinSub($s));

// This code is contributed by princiraj1992

?>

Javascript实现

输出：ss

时间复杂度：O(N)，其中N是字符串的长度。空间复杂度：O(1)