Split String

Easy
0/40
1 upvote
Asked in company
Impledge Technologies

Problem statement

You are given a string 'S' which can contain numbers or characters, and an integer 'N'.


Split the string 'S' into substrings of length 'N'. The last substring might be shorter than 'N'.


For Example : 
Let 'S' = "HelloWorld", N = 3.
The output should be "Hel", "loW ,"orl", "d".
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains the string 'S'.
The second line contains the integer 'N'.
Output Format : 
Return an array of strings, where each string is a segment of the original string 'S' of length 'N', except possibly the last one.
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
1 <= length of 'S' <= 10^5
1 <= 'N' <= length of 'S'
'S' can contain numbers as well as letters

Time Limit: 1 sec
Sample Input 1 :
ABCDEFG
2
Sample Output 1 :
AB, CD, EF, G
Explanation of sample input 1 :
The input string is "ABCDEFG" and 'N' is 2.
Splitting the string every 2 characters results in the substrings: "AB", "CD", "EF", and the remaining "G".
Thus, the answer is "AB", "CD", "EF", "G".
Sample Input 2 :
1234567890
3
Sample Output 2 :
123, 456, 789, 0
Hint

Iterate through the string with a step of 'N'.

Approaches (1)
Implementation

Approach:

  • Initialize an empty list to store the resulting substrings.
  • Iterate through the input string 'S' from the beginning to the end with a step size of 'N'.
  • In each iteration, extract a substring of length 'N' starting from the current index.
  • If the remaining part of the string is less than 'N', extract the remaining part as the last substring.
  • Add each extracted substring to the list.
  • Return the list of substrings.

Algorithm:

  • Initialize an empty list 'result'.
  • Initialize a variable 'L' to the length of the string 'S'.
  • Iterate using 'i' from 0 to 'L - 1' with a step of 'N':
    • If ( 'i' + 'N' <= 'L' ):
      • Add the substring of 'S' from index 'i' to 'i' + 'N' (exclusive) to 'result'.
    • Else:
      • Add the substring of 'S' from index 'i' to the end of 'S' to 'result'.
  • Return 'result'.
Time Complexity

O(L), where 'L' is the length of the string 'S'.

We iterate through the string 'S' once. The substring operation takes at most O(L) in some implementations, but when considered together across the loop, each character is processed a constant number of times. Thus, the overall time complexity is of the order O(L).

Space Complexity

O(K), where 'K' is the number of substrings generated, which is at most 'L'.

We are creating a list to store the substrings. In the worst case, if 'N' is 1, the number of substrings will be equal to the length of 'S'. Thus, the overall space complexity is of the order O(L) in the worst case, but can be less if 'N' is larger. So, we represent it as O(K) where K is the number of output substrings.

Code Solution
(100% EXP penalty)
Split String
Full screen
Console