Welcome to Subscribe On Youtube

1163. Last Substring in Lexicographical Order

Description

Given a string s, return the last substring of s in lexicographical order.

 

Example 1:

Input: s = "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: s = "leetcode"
Output: "tcode"

 

Constraints:

• 1 <= s.length <= 4 * 105
• s contains only lowercase English letters.

Solutions

Solution 1: Two pointers

We notice that if a substring starts from position $i$, then the largest substring with the largest dictionary order must be $s[i,..n-1]$, which is the longest suffix starting from position $i$. Therefore, we only need to find the largest suffix substring.

We use two pointers $i$ and $j$, where pointer $i$ points to the starting position of the current largest substring with the largest dictionary order, and pointer $j$ points to the starting position of the current substring being considered. In addition, we use a variable $k$ to record the current position being compared. Initially, $i=0$, $j=1$, $k=0$.

Each time, we compare $s[i+k]$ and $s[j+k]$:

If $s[i+k]=s[j+k]$, it means that $s[i,..i+k]$ and $s[j,..j+k]$ are the same, and we add $k$ by $1$ and continue to compare $s[i+k]$ and $s[j+k]$;

If $s[i+k]<s[j+k]$, it means that the dictionary order of $s[j,..j+k]$ is larger. At this time, we update $i=i+k+1$, and reset $k$ to $0$. If $i\ge j$ at this time, we update pointer $j$ to $i+1$, that is, $j=i+1$. Here we skip all suffix substrings with $s[i,..,i+k]$ as the starting position, because their dictionary orders are smaller than the suffix substrings with $s[j,..,j+k]$ as the starting position.

Similarly, if $s[i+k]>s[j+k]$, it means that the dictionary order of $s[i,..,i+k]$ is larger. At this time, we update $j=j+k+1$ and reset $k$ to $0$. Here we skip all suffix substrings with $s[j,..,j+k]$ as the starting position, because their dictionary orders are smaller than the suffix substrings with $s[i,..,i+k]$ as the starting position.

Finally, we return the suffix substring starting from $i$, that is, $s[i,..,n-1]$.

The time complexity is $O(n)$, where $n$ is the length of string $s$. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public String lastSubstring(String s) {
          int n = s.length();
          int i = 0;
          for (int j = 1, k = 0; j + k < n;) {
              int d = s.charAt(i + k) - s.charAt(j + k);
              if (d == 0) {
                  ++k;
              } else if (d < 0) {
                  i += k + 1;
                  k = 0;
                  if (i >= j) {
                      j = i + 1;
                  }
              } else {
                  j += k + 1;
                  k = 0;
              }
          }
          return s.substring(i);
      }
  }
  

• class Solution {
  public:
      string lastSubstring(string s) {
          int n = s.size();
          int i = 0;
          for (int j = 1, k = 0; j + k < n;) {
              if (s[i + k] == s[j + k]) {
                  ++k;
              } else if (s[i + k] < s[j + k]) {
                  i += k + 1;
                  k = 0;
                  if (i >= j) {
                      j = i + 1;
                  }
              } else {
                  j += k + 1;
                  k = 0;
              }
          }
          return s.substr(i);
      }
  };
  

• class Solution:
      def lastSubstring(self, s: str) -> str:
          i, j, k = 0, 1, 0
          while j + k < len(s):
              if s[i + k] == s[j + k]:
                  k += 1
              elif s[i + k] < s[j + k]:
                  i += k + 1
                  k = 0
                  if i >= j:
                      j = i + 1
              else:
                  j += k + 1
                  k = 0
          return s[i:]
  
  

• func lastSubstring(s string) string {
  	i, n := 0, len(s)
  	for j, k := 1, 0; j+k < n; {
  		if s[i+k] == s[j+k] {
  			k++
  		} else if s[i+k] < s[j+k] {
  			i += k + 1
  			k = 0
  			if i >= j {
  				j = i + 1
  			}
  		} else {
  			j += k + 1
  			k = 0
  		}
  	}
  	return s[i:]
  }
  

• function lastSubstring(s: string): string {
      const n = s.length;
      let i = 0;
      for (let j = 1, k = 0; j + k < n; ) {
          if (s[i + k] === s[j + k]) {
              ++k;
          } else if (s[i + k] < s[j + k]) {
              i += k + 1;
              k = 0;
              if (i >= j) {
                  j = i + 1;
              }
          } else {
              j += k + 1;
              k = 0;
          }
      }
      return s.slice(i);
  }
  
  

All Problems

All Solutions