String Challenges: Effective Solutions in C/C++, Java, and Python

Here's a detailed outline of string manipulation algorithms in C/C++, Java, and Python, including algorithm steps, time complexity, and space complexity.

1. Reversing a String

Algorithm Steps:

1. Input the string.

2. Initialize two pointers: one at the start (left) and one at the end (right) of the string.

3. While left < right:

   • Swap the characters at the left and right indices.

   • Increment left and decrement right.

4. Return the reversed string.

Time Complexity:

• O(n), where n is the length of the string (each character is visited once).

Space Complexity:

• O(1), since the reversal is done in place.

C++ Implementation:

#include <iostream>
#include <string>
using namespace std;

string reverseString(string str) {
    int left = 0, right = str.size() - 1;
    while (left < right) {
        swap(str[left], str[right]);
        left++;
        right--;
    }
    return str;
}

int main() {
    string str = "Hello, World!";
    cout << reverseString(str) << endl; // Output: !dlroW ,olleH
    return 0;
}

Java Implementation:

public class ReverseString {
    public static String reverseString(String str) {
        char[] charArray = str.toCharArray();
        int left = 0, right = charArray.length - 1;
        while (left < right) {
            char temp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = temp;
            left++;
            right--;
        }
        return new String(charArray);
    }

    public static void main(String[] args) {
        String str = "Hello, World!";
        System.out.println(reverseString(str)); // Output: !dlroW ,olleH
    }
}

Python Implementation:

def reverse_string(s):
    return s[::-1]

s = "Hello, World!"
print(reverse_string(s))  # Output: !dlroW ,olleH

2. Checking if a String is a Palindrome

Algorithm Steps:

1. Input the string.

2. Initialize two pointers: one at the start (left) and one at the end (right) of the string.

3. While left < right:

   • If characters at left and right are not equal, return false.

   • Increment left and decrement right.

4. Return true after checking all characters.

Time Complexity:

• O(n), where n is the length of the string.

Space Complexity:

• O(1), as no additional data structures are used.

C++ Implementation:

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(string str) {
    int left = 0, right = str.size() - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string str = "racecar";
    cout << (isPalindrome(str) ? "True" : "False") << endl; // Output: True
    return 0;
}

Java Implementation:

public class PalindromeCheck {
    public static boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String str = "racecar";
        System.out.println(isPalindrome(str)); // Output: true
    }
}

Python Implementation:

def is_palindrome(s):
    return s == s[::-1]

s = "racecar"
print(is_palindrome(s))  # Output: True

3. Finding the Length of the Longest Substring Without Repeating Characters

Algorithm Steps:

1. Initialize a hash map to store the last index of each character.

2. Initialize two pointers: left and right to track the substring's start and end.

3. Initialize maxLength to 0.

4. While right is less than the length of the string:

   • If the character at right is already in the hash map and its index is greater than or equal to left, move left to the right of the character's last index.

   • Update the character's index in the hash map to the current right index.

   • Update maxLength as the maximum of maxLength and the length of the current substring (right - left + 1).

   • Increment right.

5. Return maxLength.

Time Complexity:

• O(n), where n is the length of the string.

Space Complexity:

• O(min(m, n)), where m is the size of the character set and n is the length of the string.

C++ Implementation:

#include <iostream>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> charIndex;
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.size(); right++) {
        if (charIndex.find(s[right]) != charIndex.end()) {
            left = max(left, charIndex[s[right]] + 1);
        }
        charIndex[s[right]] = right;
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    string s = "abcabcbb";
    cout << lengthOfLongestSubstring(s) << endl; // Output: 3
    return 0;
}

Java Implementation:

import java.util.HashMap;

public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> charIndex = new HashMap<>();
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            if (charIndex.containsKey(s.charAt(right))) {
                left = Math.max(left, charIndex.get(s.charAt(right)) + 1);
            }
            charIndex.put(s.charAt(right), right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s)); // Output: 3
    }
}

Python Implementation:

def length_of_longest_substring(s):
    char_index = {}
    left = max_length = 0

    for right in range(len(s)):
        if s[right] in char_index:
            left = max(left, char_index[s[right]] + 1)
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)

    return max_length

s = "abcabcbb"
print(length_of_longest_substring(s))  # Output: 3

4. Counting the Number of Vowels in a String

Algorithm Steps:

1. Initialize a variable count to 0.

2. Loop through each character in the string:

   • If the character is a vowel (a, e, i, o, u), increment count.

3. Return count.

Time Complexity:

• O(n), where n is the length of the string.

Space Complexity:

• O(1), as only a counter is used.

C++ Implementation:

#include <iostream>
#include <string>
using namespace std;

int countVowels(string str) {
    int count = 0;
    for (char c : str) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
            c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
            count++;
        }
    }
    return count;
}

int main() {
    string str = "Hello, World!";
    cout << countVowels(str) << endl; // Output: 3
    return 0;
}

Java Implementation:

public class CountVowels {
    public static int countVowels(String str) {
        int count = 0;
        for (char c : str.toCharArray()) {
            if ("aeiouAEIOU".indexOf(c) != -1) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String str = "Hello, World!";
        System.out.println(countVowels(str)); // Output: 3
    }
}

Python Implementation:

def count_vowels(s):
    count = sum(1 for char in s if char.lower() in 'aeiou')
    return count

s = "Hello, World!"
print(count_vowels(s))  # Output: 3

Given a string, the task is to compress it by replacing sequences of the same character with that character followed by the number of times it appears consecutively. For example, the string "aabcccccaaa" would become "a2b1c5a3". If the compressed string is not shorter than the original string, the original string should be returned.

Algorithm:

1. Initialize Variables:

   • Create an empty result string (or list) to store the compressed version.

   • Initialize a counter to count the occurrences of consecutive characters.

2. Iterate Through the String:

   • Traverse the string character by character.

   • For each character, increment the counter.

   • If the next character is different from the current one or the end of the string is reached, append the current character and its count to the result string.

   • Reset the counter for the next character.

3. Finalize the Compressed String:

   • After iterating through the string, check if the length of the compressed string is shorter than the original string.

   • If it is, return the compressed string; otherwise, return the original string.

Code Implementations:

Python Implementation:

def compress_string(s):
    if not s:
        return ""

    compressed = []
    count = 1

    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            compressed.append(s[i - 1] + str(count))
            count = 1

    # Append the last character and its count
    compressed.append(s[-1] + str(count))

    compressed_string = ''.join(compressed)

    return compressed_string if len(compressed_string) < len(s) else s

# Example usage
input_str = "aabcccccaaa"
print("Compressed string:", compress_string(input_str))

Java Implementation:

public class StringCompression {
    public static String compressString(String s) {
        if (s == null || s.isEmpty()) {
            return s;
        }

        StringBuilder compressed = new StringBuilder();
        int count = 1;

        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count++;
            } else {
                compressed.append(s.charAt(i - 1)).append(count);
                count = 1;
            }
        }

        // Append the last character and its count
        compressed.append(s.charAt(s.length() - 1)).append(count);

        return compressed.length() < s.length() ? compressed.toString() : s;
    }

    public static void main(String[] args) {
        String inputStr = "aabcccccaaa";
        System.out.println("Compressed string: " + compressString(inputStr));
    }
}

C/C++ Implementation:

#include <stdio.h>
#include <string.h>

char* compress_string(char* s) {
    if (s == NULL || strlen(s) == 0) {
        return s;
    }

    static char compressed[1000]; // Adjust size as needed
    int compressed_index = 0;
    int count = 1;

    for (int i = 1; i < strlen(s); i++) {
        if (s[i] == s[i - 1]) {
            count++;
        } else {
            compressed_index += sprintf(&compressed[compressed_index], "%c%d", s[i - 1], count);
            count = 1;
        }
    }

    // Append the last character and its count
    sprintf(&compressed[compressed_index], "%c%d", s[strlen(s) - 1], count);

    // Return original string if compressed is not shorter
    return strlen(compressed) < strlen(s) ? compressed : s;
}

int main() {
    char input_str[] = "aabcccccaaa";
    printf("Compressed string: %s\n", compress_string(input_str));
    return 0;
}

Detailed Explanation:

1. Python Implementation:

   • StringBuilder Alternative: In Python, lists are used to build strings incrementally because they are more efficient than repeatedly concatenating strings.

   • Appending Characters: Characters and their counts are added to the list, which is then joined into a final string.

   • Efficiency: Python’s list operations are efficient, making this implementation both time-efficient and easy to understand.

2. Java Implementation:

   • StringBuilder: Java's StringBuilder is used because it is more efficient than String for repeated concatenation.

   • Looping Through Characters: The loop starts at the second character, comparing each character to the previous one to count consecutive characters.

   • Final Check: After constructing the compressed string, it is compared to the original, and the shorter one is returned.

3. C/C++ Implementation:

   • Static Array: A static array is used to store the compressed string. Adjust its size based on expected input to avoid overflow.

   • sprintf for Concatenation: The sprintf function is used to format and append characters and their counts to the compressed string.

   • Final Comparison: The final compressed string is compared with the original, returning the shorter one.

Time Complexity:

• The time complexity for this algorithm is O(n), where n is the length of the string, as it requires a single pass to compress the string.

Space Complexity:

• The space complexity is O(n) since the maximum size of the compressed string can be proportional to the length of the input string

6.Find the First Non-Repeating Character in a String

Algorithm:

To solve the problem of finding the first non-repeating character in a string, we can use the following steps:

Steps:

1. Initialize Data Structures:

   • Use a hash map (or dictionary) to store the count of each character in the string.

   • Another option is to use an array if the character set is small and known (e.g., ASCII).

2. First Pass - Counting Occurrences:

   • Traverse the string from left to right.

   • For each character in the string, increment its count in the hash map.

   • This pass will help us determine how many times each character appears in the string.

3. Second Pass - Find the First Non-Repeating Character:

   • Traverse the string again from left to right.

   • For each character, check its count in the hash map.

   • The first character with a count of 1 is the first non-repeating character.

4. Return the Result:

   • If a non-repeating character is found, return it.

   • If no non-repeating character exists, return a special value (like None or a specific message).

Code Implementations:

Python Implementation:

def first_non_repeating_character(s):
    # Step 1: Initialize the hash map (dictionary)
    char_count = {}

    # Step 2: First pass to count occurrences of each character
    for c in s:
        if c in char_count:
            char_count[c] += 1
        else:
            char_count[c] = 1

    # Step 3: Second pass to find the first non-repeating character
    for c in s:
        if char_count[c] == 1:
            return c

    # Step 4: Return result if no non-repeating character is found
    return None

# Example usage
str_input = "swiss"
result = first_non_repeating_character(str_input)
if result:
    print("First non-repeating character:", result)
else:
    print("No non-repeating character found.")

Java Implementation:

import java.util.HashMap;

public class FirstNonRepeating {
    public static Character firstNonRepeatingCharacter(String s) {
        // Step 1: Initialize the hash map
        HashMap<Character, Integer> charCount = new HashMap<>();

        // Step 2: First pass to count occurrences of each character
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // Step 3: Second pass to find the first non-repeating character
        for (char c : s.toCharArray()) {
            if (charCount.get(c) == 1) {
                return c;
            }
        }

        // Step 4: Return result if no non-repeating character is found
        return null;
    }

    public static void main(String[] args) {
        String str = "swiss";
        Character result = firstNonRepeatingCharacter(str);
        if (result != null) {
            System.out.println("First non-repeating character: " + result);
        } else {
            System.out.println("No non-repeating character found.");
        }
    }
}

C/C++ Implementation:

#include <stdio.h>
#include <string.h>

char firstNonRepeatingCharacter(char *s) {
    // Step 1: Initialize the array to store counts (assuming ASCII character set)
    int charCount[256] = {0};

    // Step 2: First pass to count occurrences of each character
    for (int i = 0; s[i]; i++) {
        charCount[s[i]]++;
    }

    // Step 3: Second pass to find the first non-repeating character
    for (int i = 0; s[i]; i++) {
        if (charCount[s[i]] == 1) {
            return s[i];
        }
    }

    // Step 4: Return result if no non-repeating character is found
    return '\0'; // Indicates no non-repeating character found
}

int main() {
    char str[] = "swiss";
    char result = firstNonRepeatingCharacter(str);
    if (result) {
        printf("First non-repeating character: %c\n", result);
    } else {
        printf("No non-repeating character found.\n");
    }
    return 0;
}

Time Complexity:

• The time complexity for this algorithm is O(n), where n is the length of the string. This is because both passes over the string are O(n) operations.

Space Complexity:

• The space complexity is O(1) if the character set is fixed (e.g., ASCII), as the size of the hash map or array is constant. For a more extensive character set (e.g., Unicode), the space complexity would be O(k), where k is the number of distinct characters.