给定一个字符串，我们必须找到该字符串的字典最大子字符串
null
例如：
Input : s = "ababaa"Output : babaaExplanation : "babaa" is the maximum lexicographic substring formed from this stringInput : s = "asdfaa"Output : sdfaa
这个想法很简单，我们遍历所有的子字符串。对于每个子字符串，我们将其与当前结果进行比较，并在需要时更新结果。
以下是实施情况：
C++
// CPP program to find the lexicographically // maximum substring. #include <bits/stdc++.h> using namespace std; string LexicographicalMaxString(string str) { // loop to find the max lexicographic // substring in the substring array string mx = "" ; for ( int i = 0; i < str.length(); ++i) mx = max(mx, str.substr(i)); return mx; } // Driver code int main() { string str = "ababaa" ; cout << LexicographicalMaxString(str); return 0; } |
JAVA
// Java program to find the lexicographically // maximum substring. class GFG { static String LexicographicalMaxString(String str) { // loop to find the max lexicographic // substring in the substring array String mx = "" ; for ( int i = 0 ; i < str.length(); ++i) { if (mx.compareTo(str.substring(i)) <= 0 ) { mx = str.substring(i); } } return mx; } // Driver code public static void main(String[] args) { String str = "ababaa" ; System.out.println(LexicographicalMaxString(str)); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program to find the # lexicographically maximum substring. def LexicographicalMaxString( str ): # loop to find the max lexicographic # substring in the substring array mx = "" for i in range ( len ( str )): mx = max (mx, str [i:]) return mx # Driver code if __name__ = = '__main__' : str = "ababaa" print (LexicographicalMaxString( str )) # This code is contributed by # Sanjit_Prasad |
C#
// C# program to find the lexicographically // maximum substring. using System; public class GFG { static String LexicographicalMaxString(String str) { // loop to find the max lexicographic // substring in the substring array String mx = "" ; for ( int i = 0; i < str.Length; ++i) { if (mx.CompareTo(str.Substring(i)) <= 0) { mx = str.Substring(i); } } return mx; } // Driver code public static void Main() { String str = "ababaa" ; Console.WriteLine(LexicographicalMaxString(str)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find the lexicographically // maximum substring. function LexicographicalMaxString(str) { // loop to find the max lexicographic // substring in the substring array var mx = "" ; for ( var i = 0; i < str.length; ++i) { if (mx.localeCompare(str.substring(i)) <= 0) { mx = str.substring(i); } } return mx; } // Driver code var str = "ababaa" ; document.write(LexicographicalMaxString(str)); // This code is contributed by 29AjayKumar </script> |
输出：
babaa
优化： 我们找到最大的字符及其所有索引。现在我们只需遍历最大字符的所有实例，就可以找到按字典顺序排列的最大子字符串。
这里我们遵循上述方法。
C++
// C++ program to find the lexicographically // maximum substring. #include <bits/stdc++.h> using namespace std; string LexicographicalMaxString(string str) { char maxchar = 'a' ; vector< int > index; // We store all the indexes of maximum // characters we have in the string for ( int i = 0; i < str.length(); i++) { if (str[i] >= maxchar) { maxchar = str[i]; index.push_back(i); } } string maxstring = "" ; // We form a substring from that maximum // character index till end and check if // its greater that maxstring for ( int i = 0; i < index.size(); i++) { if (str.substr(index[i], str.length()) > maxstring) { maxstring = str.substr(index[i], str.length()); } } return maxstring; } // Driver code int main() { string str = "acbacbc" ; cout << LexicographicalMaxString(str); return 0; } |
JAVA
// Java program to find the lexicographically // maximum substring. import java.io.*; import java.util.*; class GFG { static String LexicographicalMaxString(String str) { char maxchar = 'a' ; ArrayList<Integer> index = new ArrayList<Integer>(); // We store all the indexes of maximum // characters we have in the string for ( int i = 0 ; i < str.length(); i++) { if (str.charAt(i) >= maxchar) { maxchar = str.charAt(i); index.add(i); } } String maxstring = "" ; // We form a substring from that maximum // character index till end and check if // its greater that maxstring for ( int i = 0 ; i < index.size(); i++) { if (str.substring(index.get(i), str.length()).compareTo( maxstring) > 0 ) { maxstring = str.substring(index.get(i), str.length()); } } return maxstring; } // Driver code public static void main (String[] args) { String str = "acbacbc" ; System.out.println(LexicographicalMaxString(str)); } } // This code is contributed by rag2127. |
Python3
# Python 3 program to find # the lexicographically # maximum substring. def LexicographicalMaxString(st): maxchar = 'a' index = [] # We store all the indexes # of maximum characters we # have in the string for i in range ( len (st)): if (st[i] > = maxchar): maxchar = st[i] index.append(i) maxstring = "" # We form a substring from that # maximum character index till # end and check if its greater # that maxstring for i in range ( len (index)): if (st[index[i]: len (st)] > maxstring): maxstring = st[index[i]: len (st)] return maxstring # Driver code if __name__ = = "__main__" : st = "acbacbc" print (LexicographicalMaxString(st)) # This code is contributed by Chitranayal |
C#
// C# program to find the lexicographically // maximum substring. using System; using System.Collections.Generic; class GFG{ static string LexicographicalMaxString( string str) { char maxchar = 'a' ; List< int > index = new List< int >(); // We store all the indexes of maximum // characters we have in the string for ( int i = 0; i < str.Length; i++) { if (str[i] >= maxchar) { maxchar = str[i]; index.Add(i); } } string maxstring = "" ; // We form a substring from that maximum // character index till end and check if // its greater that maxstring for ( int i = 0; i < index.Count; i++) { if (str.Substring(index[i]).CompareTo(maxstring) > 0) { maxstring = str.Substring(index[i]); } } return maxstring; } // Driver code static public void Main() { string str = "acbacbc" ; Console.Write(LexicographicalMaxString(str)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program to find the lexicographically // maximum substring. function LexicographicalMaxString(str) { let maxchar = 'a' ; let index = []; // We store all the indexes of maximum // characters we have in the string for (let i = 0; i < str.length; i++) { if (str[i] >= maxchar) { maxchar = str[i]; index.push(i); } } let maxstring = "" ; // We form a substring from that maximum // character index till end and check if // its greater that maxstring for (let i = 0; i < index.length; i++) { if (str.substring(index[i], str.length) > maxstring) { maxstring = str.substring(index[i], str.length); } } return maxstring; } // Driver code let str = "acbacbc" ; document.write(LexicographicalMaxString(str)); // This code is contributed by ab2127 </script> |
输出：
cbc
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
