You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.
s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".Return the modified string after the spaces have been added.
Example 1:
Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15] Output: "Leetcode Helps Me Learn" Explanation: The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn". We then place spaces before those characters.
Example 2:
Input: s = "icodeinpython", spaces = [1,5,7,9] Output: "i code in py thon" Explanation: The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython". We then place spaces before those characters.
Example 3:
Input: s = "spacing", spaces = [0,1,2,3,4,5,6] Output: " s p a c i n g" Explanation: We are also able to place spaces before the first character of the string.
Constraints:
1 <= s.length <= 3 * 105s consists only of lowercase and uppercase English letters.1 <= spaces.length <= 3 * 1050 <= spaces[i] <= s.length - 1spaces are strictly increasing.This approach involves checking all possible combinations or permutations to find the solution. Although it's straightforward and easy to implement, it may not be the most efficient way due to its high time complexity.
This C program sets up a framework for a brute-force solution. Currently, the logic is not implemented, but the structure is in place to solve the problem by iterating over possible solutions.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) - where n is the size of the input.
Space Complexity: O(1) - constant space usage as no additional data structures are used.
This approach uses a hash map to store intermediate results or counts, allowing for quicker lookup and more efficient processing, reducing the time complexity compared to the brute-force method.
This C program outlines the structure for utilizing a hash map approach to optimize solving the problem.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - linear time if hash lookups are constant time.
Space Complexity: O(n) - due to storage in the hash map.
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n^2) - where n is the size of the input. |
| Approach 2: Optimized Solution Using Hash Map | Time Complexity: O(n) - linear time if hash lookups are constant time. |
Adding Spaces to a String - Leetcode 2109 - Python • NeetCodeIO • 6,496 views views
Watch 9 more video solutions →Practice Adding Spaces to a String with our built-in code editor and test cases.
Practice on FleetCode