- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a string s with only numbers. We have to check whether we can split s into two or more non-empty substrings such that the numerical values of those substrings are in non-increasing sequence and the difference between numerical values of every two adjacent substrings is 1. So for example, if the string is s = "0080079" we can split it into ["0080", "079"] with numerical values [80, 79]. And the values are in descending order and adjacent values differ by 1, so this way is valid. We have to check whether it is possible to split s as described above, or not.

So, if the input is like s = "080076", then the output will be True because we can split it like ["08", "007", "6"], so numeric values are [8,7,6].

To solve this, we will follow these steps −

Define a function dfs() . This will take s, pre, idx, n

if pre is not -1 and integer form of (substring of s[from index idx to end]) is same as pre -1, then

return True

for i in range 1 to n-idx-1, do

curs := substring of s[from index idx to idx+i-1]

cur := curs as number

if pre is same as -1, then

if dfs(s, cur, idx+i, n) is true, then

return True

otherwise,

if cur is same as pre - 1 and dfs(s, cur, idx+i, n) is true, then

return True

return False

From the main method, do the following

n := size of s

if n <= 1, then

return False

return dfs(s, -1, 0, n)

Let us see the following implementation to get better understanding −

def dfs(s, pre, idx, n): if pre != -1 and int(s[idx:]) == pre - 1: return True for i in range(1, n-idx): curs = s[idx: idx+i] cur = int(curs) if pre == -1: if dfs(s, cur, idx+i, n): return True else: if cur == pre - 1 and dfs(s, cur, idx+i, n): return True return False def solve(s): n = len(s) if n <= 1: return False return dfs(s, -1, 0, n) s = "080076" print(solve(s))

"080076"

True

- Related Questions & Answers
- Program to check whether we can split list into consecutive increasing sublists or not in Python
- Program to check a string can be split into three palindromes or not in Python
- Can split array into consecutive subsequences in JavaScript
- Program to check whether one string can be 1-to-1 mapped into another string in Python
- Program to check whether list can be split into sublists of k increasing elements in C++
- Program to check whether we can convert string in K moves or not using Python
- How we can split Python class into multiple files?
- Check if given string can be split into four distinct strings in Python
- Python program to split string into k distinct partitions
- Python program to check whether we can pile up cubes or not
- Program to check string contains consecutively descending string or not in Python
- How to split a vector into smaller vectors of consecutive values in R?\n
- Program to check whether we can take all courses or not in Python
- Program to check whether we can unlock all rooms or not in python
- Program to check whether we can form 24 by placing operators in python

Advertisements