Remaining String

Given a string s without spaces, a character ch and an integer count. Your task is to return the substring that remains after the character ch has appeared count number of times.
Note:  Assume upper case and lower case alphabets are different. “”(Empty string) should be returned if it is not possible, or the remaining substring is empty.

Examples:

Input: s = "Thisisdemostring", ch = 'i', count = 3
Output: ng
Explanation: The remaining substring of s after the 3rd
occurrence of 'i' is "ng", hence the output is ng.

Input: s = "Thisisdemostri", ch = 'i', count = 3
Output: ""
Explanation: The 3rd occurence of 'i' is at the last index. In this case the remaining substring is empty, hence we return empty string.

Input: s = "abcd", ch = 'x', count = 2
Output: ""
Explanation: The character x is not present in the string, hence we return empty string.

Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(1)

Constraints:
1<= s.length()<=10⁵
1<=count<=s.length()
s[i] is both upper case and lower case

Approach 01:

#include <string>
using namespace std;

class Solution {
public:
    string printString(string s, char ch, int count) {
        int n = s.length();
        int i = 0;

        for (i = 0; i < n; i++) {
            if (count == 0) {
                break;
            }
            if (s[i] == ch) {
                count--;
            }
        }

        string result = s.substr(i, n - i);
        return result;
    }
};

class Solution:
    def printString(self, s, ch, count):
        n = len(s)
        i = 0
        for i in range(n):
            if(count == 0):
                break
            if(s[i] == ch):
                count -= 1
            i += 1
        result = s[i:n]
        return result

Time Complexity

• Iteration through the string:

  The loop iterates through the string once, making the time complexity \( O(n) \), where n is the length of the string s.

• Substr operation:

  The substr function takes \( O(n) \) time as it needs to copy a portion of the string.

• Overall Time Complexity:

  The overall time complexity is \( O(n) \).

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of additional space for variables i, n, and count, resulting in \( O(1) \) space usage.

• Result Storage:

  The substr function creates a new string, which can be up to the length of s. Therefore, it uses \( O(n) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \).