Sponsored
Sponsored
The two pointers approach uses two indices to represent the start and end of the string. The idea is to check for matching characters from both ends and shrink the string until the characters differ. Loop through the string, adjusting these pointers to remove any prefixes and suffixes with matching characters. This method is efficient as it only requires a single pass through the string.
Time Complexity: O(n), where n is the length of the string, because each character is visited at most twice.
Space Complexity: O(1), as no additional space is used apart from variables.
1#include <stdio.h>
2#include <string.h>
3
4int minimumLength(char *s) {
5 int n = strlen(s);
6 int left = 0, right = n - 1;
7 while (left < right && s[left] == s[right]) {
8 char currentChar = s[left];
9 while (left <= right && s[left] == currentChar) {
10 left++;
11 }
12 while (left <= right && s[right] == currentChar) {
13 right--;
14 }
15 }
16 return right - left + 1;
17}
18
19int main() {
20 char s[] = "aabccabba";
21 printf("%d\n", minimumLength(s)); // Output: 3
22 return 0;
23}This C implementation uses a two-pointer approach to achieve the goal. Two pointers, left and right, are initialized at the start and end of the string, respectively. As long as the characters at these pointers match, both pointers are adjusted inward until they meet or characters differ. The remaining string length is calculated and returned as the result.
This recursive approach tries to minimize the string length by removing valid prefixes and suffixes. The base case is when no more valid removals are possible, and the remaining string length is minimal. Each recursive call attempts to strip away the symmetric ends and proceeds with the interior until the results match.
Time Complexity: O(n), since it navigates through the string at minimal overhead.
Space Complexity: O(n) due to recursion depth management.
#include <string>
int recursiveLength(const std::string &s, int left, int right) {
if (left >= right) return right - left + 1;
if (s[left] != s[right]) return right - left + 1;
char currentChar = s[left];
while (left <= right && s[left] == currentChar) {
left++;
}
while (left <= right && s[right] == currentChar) {
right--;
}
return recursiveLength(s, left, right);
}
int minimumLength(std::string s) {
return recursiveLength(s, 0, s.size() - 1);
}
int main() {
std::string s = "aabccabba";
std::cout << minimumLength(s) << std::endl; // Output: 3
return 0;
}The C++ solution employs recursion, handling characters at opposite ends of the string. It evaluates prefix-suffix symmetry and continues further recursive explorations, removing sections upon valid match elimination.