1849. Splitting a String Into Descending Consecutive Values LeetCode Solution
In this guide, you will get 1849. Splitting a String Into Descending Consecutive Values LeetCode Solution with the best time and space complexity. The solution to Splitting a String Into Descending Consecutive Values problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Splitting a String Into Descending Consecutive Values
You are given a string s that consists of only digits.
Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.
For example, the string s = “0090089” can be split into [“0090”, “089”] with numerical values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is valid.
Another example, the string s = “001” can be split into [“0”, “01”], [“00”, “1”], or [“0”, “0”, “1”]. However all the ways are invalid because they have numerical values [0,1], [0,1], and [0,0,1] respectively, all of which are not in descending order.
Return true if it is possible to split s as described above, or false otherwise.
A substring is a contiguous sequence of characters in a string.
Input: s = “1234”
Output: false
Explanation: There is no valid way to split s.
Example 2:
Input: s = “050043”
Output: true
Explanation: s can be split into [“05”, “004”, “3”] with numerical values [5,4,3].
The values are in descending order with adjacent values differing by 1.
Example 3:
Input: s = “9080701”
Output: false
Explanation: There is no valid way to split s.
Constraints:
1 <= s.length <= 20
s only consists of digits.
Complexity Analysis
Time Complexity: O(2^n)
Space Complexity: O(n)
1849. Splitting a String Into Descending Consecutive Values LeetCode Solution in C++
class Solution {
public:
bool splitString(string s) {
return isValid(s, 0, -1, 0);
}
private:
bool isValid(const string& s, int start, long prev, int segment) {
if (start == s.length() && segment > 1)
return true;
long curr = 0;
for (int i = start; i < s.length(); ++i) {
curr = curr * 10 + s[i] - '0';
if (curr > 9999999999L)
return false;
if ((prev == -1 || curr == prev - 1) &&
isValid(s, i + 1, curr, segment + 1)) {
return true;
}
}
return false;
}
}; /* code provided by PROGIEZ */
1849. Splitting a String Into Descending Consecutive Values LeetCode Solution in Java
class Solution {
public boolean splitString(String s) {
return isValid(s, 0, -1, 0);
}
private boolean isValid(final String s, int start, long prev, int segment) {
if (start == s.length() && segment > 1)
return true;
long curr = 0;
for (int i = start; i < s.length(); ++i) {
curr = curr * 10 + s.charAt(i) - '0';
if (curr > 9999999999)
return false;
if ((prev == -1 || curr == prev - 1) && isValid(s, i + 1, curr, segment + 1))
return true;
}
return false;
}
} // code provided by PROGIEZ
1849. Splitting a String Into Descending Consecutive Values LeetCode Solution in Python
class Solution:
def splitString(self, s: str) -> bool:
def isValid(s: str, start: int, prev: int, segment: int) -> bool:
if start == len(s) and segment > 1:
return True
curr = 0
for i in range(start, len(s)):
curr = curr * 10 + int(s[i])
if curr > 9999999999:
return False
if (prev == -1 or curr == prev - 1) and isValid(s, i + 1, curr, segment + 1):
return True
return False
return isValid(s, 0, -1, 0) # code by PROGIEZ
