Advertisement
3403. Find the Lexicographically Largest String From the Box I
UnknownView on LeetCode
Time: O(n²)
Space: O(1)
Approach
Find lex-largest substring of length max(1, n - numFriends + 1) by direct scan.
3403.cs
C#
// Approach: Find lex-largest substring of length max(1, n - numFriends + 1) by direct scan.
// Time: O(n²) Space: O(1)
public class Solution
{
public string AnswerString(string word, int numFriends)
{
// If there is only one friend, return the whole word as is.
if (numFriends == 1)
return word;
int wordLength = word.Length;
string answer = "";
// Iterate over each character of the word.
for (int i = 0; i < wordLength; ++i)
{
// Determine the maximum substring length that can be taken starting from the current position.
int maxSubstringLength = Math.Min(wordLength - i, wordLength - numFriends + 1);
// Extract the substring starting at position i with the determined length.
string currentSubstring = word.Substring(i, maxSubstringLength);
// Compare the current substring with the answer found so far and update if it is greater.
if (string.Compare(answer, currentSubstring) < 0)
answer = currentSubstring;
}
// Return the largest lexicographical substring found.
return answer;
}
}Advertisement
Was this solution helpful?