4.3 Developing Algorithms Using Strings

Strings are one of the most common data types used in programming, representing text data from user inputs to file contents. Developing algorithms to process, analyze, and manipulate strings is a fundamental skill in computer science. This guide explores standard algorithms for string processing and provides examples of how to implement and modify these algorithms for various purposes. By mastering these techniques, you'll be able to solve complex string-related problems efficiently.

String Basics Review

Before diving into algorithms, let's review some key properties of strings in Java:

• Strings are objects in Java, not primitive types
• String objects are immutable (cannot be changed after creation)
• The String class provides many built-in methods for manipulation
• Strings can be compared using the equals method rather than the <highlight> operator
• Characters in a string are indexed starting from 0

String greeting = "Hello, World!";
int length = greeting.length();  // 13
char firstChar = greeting.charAt(0);  // 'H'
char lastChar = greeting.charAt(greeting.length() - 1);  // '!'

// Using the equals method for content comparison
String str1 = "Hello";
String str2 = "Hello";
if (str1.equals(str2)) {  // true
    System.out.println("The strings have the same content");
}

Standard String Algorithms

1. Finding Substrings

A common task is checking if a string contains a particular substring. Java provides built-in methods, but understanding the algorithm helps in developing custom search functions:

// Using built-in method
String text = "Programming is fun and educational";
boolean contains = text.contains("fun");  // true

// Custom implementation to search for substrings
public static boolean containsSubstring(String str, String sub) {
    for (int i = 0; i <= str.length() - sub.length(); i++) {
        boolean found = true;
        for (int j = 0; j < sub.length(); j++) {
            if (str.charAt(i + j) != sub.charAt(j)) {
                found = false;
                break;
            }
        }
        if (found) return true;
    }
    return false;
}

2. Counting Occurrences of a Substring

Counting how many times a particular substring appears in a text is useful for text analysis:

// Count occurrences of a substring
public static int countOccurrences(String text, String sub) {
    int count = 0;
    int index = 0;
    
    while ((index = text.indexOf(sub, index)) != -1) {
        count++;
        index += sub.length();
    }
    
    return count;
}

3. Reversing a String

The reverse operation creates a new string with the characters in opposite order. This is commonly used in palindrome checking and other text transformations:

public static String reverseString(String str) {
    String reversed = "";
    for (int i = str.length() - 1; i >= 0; i--) {
        reversed += str.charAt(i);
    }
    return reversed;
}

// More efficient implementation using StringBuilder
public static String reverseStringEfficient(String str) {
    StringBuilder sb = new StringBuilder(str);
    return sb.reverse().toString();
}

Implementing String Algorithms with Loops

Most string processing algorithms rely on loops to iterate through characters. The for loop is particularly well-suited for string operations because strings have a known length.

String Traversal

A basic string traversal visits each character in sequence:

String text = "algorithm";
for (int i = 0; i < text.length(); i++) {
    char c = text.charAt(i);
    System.out.println("Character at position " + i + ": " + c);
}

The loop initialization (int i = 0) sets the starting position at the beginning of the string, and the loop increment (i++) moves to the next character in each iteration.

Finding Characters with Specific Properties

This algorithm searches for characters meeting certain criteria:

// Count vowels in a string
public static int countVowels(String str) {
    int count = 0;
    String vowels = "aeiouAEIOU";
    
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (vowels.indexOf(c) != -1) {
            count++;
        }
    }
    
    return count;
}

Advanced String Algorithms

1. Palindrome Checking

A palindrome reads the same forward and backward (e.g., "radar"). This algorithm checks if a string is a palindrome:

public static boolean isPalindrome(String str) {
    // Remove spaces and convert to lowercase for more flexible matching
    str = str.replaceAll("\\s+", "").toLowerCase();
    
    int left = 0;
    int right = str.length() - 1;
    
    while (left < right) {
        if (str.charAt(left) != str.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

2. Finding the Longest Substring Without Repeating Characters

This algorithm uses a technique called the sliding window approach. The sliding window is a conceptual subset of elements that "slides" through an array or string, allowing us to process subarrays or substrings efficiently:

public static String longestSubstringWithoutRepeats(String str) {
    if (str.length() <= 1) return str;
    
    boolean[] seen = new boolean[256]; // Assumes ASCII
    int[] lastPos = new int[256];
    int start = 0;
    int maxLength = 0;
    int maxStart = 0;
    
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        
        if (seen[c] && lastPos[c] >= start) {
            // Update start to position after the last occurrence
            start = lastPos[c] + 1;
        }
        
        // Check if current substring is longer than the maximum found
        if (i - start + 1 > maxLength) {
            maxLength = i - start + 1;
            maxStart = start;
        }
        
        seen[c] = true;
        lastPos[c] = i;
    }
    
    return str.substring(maxStart, maxStart + maxLength);
}

3. String Compression

This algorithm compresses a string by replacing repeated characters with the character followed by the count:

public static String compressString(String str) {
    if (str </highlight> null || str.isEmpty()) return str;
    
    StringBuilder compressed = new StringBuilder();
    char currentChar = str.charAt(0);
    int count = 1;
    
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) <highlight> currentChar) {
            count++;
        } else {
            compressed.append(currentChar);
            compressed.append(count);
            currentChar = str.charAt(i);
            count = 1;
        }
    }
    
    // Add the last character and count
    compressed.append(currentChar);
    compressed.append(count);
    
    // Return the original string if compression didn't help
    return compressed.length() < str.length() ? compressed.toString() : str;
}

Practical String Algorithm Examples

1. Checking for Anagrams

Anagrams are words or phrases formed by rearranging the letters of another:

public static boolean areAnagrams(String str1, String str2) {
    // Remove spaces and convert to lowercase
    str1 = str1.replaceAll("\\s+", "").toLowerCase();
    str2 = str2.replaceAll("\\s+", "").toLowerCase();
    
    // Quick check for length
    if (str1.length() != str2.length()) return false;
    
    // Count character frequencies
    int[] counts = new int[26];
    
    for (int i = 0; i < str1.length(); i++) {
        counts[str1.charAt(i) - 'a']++;
        counts[str2.charAt(i) - 'a']--;
    }
    
    // Check if all counts are zero
    for (int count : counts) {
        if (count != 0) return false;
    }
    
    return true;
}

2. Finding All Permutations of a String

This recursive algorithm generates all possible arrangements of characters:

public static void findPermutations(String str) {
    findPermutationsHelper("", str);
}

private static void findPermutationsHelper(String prefix, String remaining) {
    int n = remaining.length();
    
    if (n </highlight> 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            findPermutationsHelper(
                prefix + remaining.charAt(i),
                remaining.substring(0, i) + remaining.substring(i + 1, n)
            );
        }
    }
}

3. Creating a Caesar Cipher

This algorithm shifts each letter in a string by a fixed number of positions:

public static String caesarCipher(String str, int shift) {
    StringBuilder result = new StringBuilder();
    
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        
        if (Character.isLetter(c)) {
            char base = Character.isUpperCase(c) ? 'A' : 'a';
            c = (char)(((c - base + shift) % 26) + base);
        }
        
        result.append(c);
    }
    
    return result.toString();
}

Algorithm Efficiency Considerations

When developing string algorithms, consider these efficiency tips:

1. StringBuilder vs. String Concatenation

   // Inefficient for many concatenations
   String result = "";
   for (int i = 0; i < 1000; i++) {
       result += "a";
   }
   
   // Much more efficient
   StringBuilder result = new StringBuilder();
   for (int i = 0; i < 1000; i++) {
       result.append("a");
   }
   String finalResult = result.toString();
   

2. Avoid Unnecessary String Creation

   // Inefficient - creates many intermediate strings
   String str = "original";
   for (int i = 0; i < str.length(); i++) {
       str = str.substring(1) + str.charAt(0);
   }
   
   // More efficient - store characters in a different structure
   char[] chars = str.toCharArray();
   // Manipulate the character array instead
   

3. Use Built-in Methods When Appropriate

   // Built-in methods are often optimized
   String reversed = new StringBuilder(str).reverse().toString();
   boolean containsText = str.contains("search text");
   

Key Takeaways

• String algorithms often involve traversing characters using loops
• The equals method should be used for string comparison, not the == operator
• Loop initialization and loop increment are key components in string traversal algorithms
• Reversing strings is a common operation that can be implemented efficiently using StringBuilder
• The sliding window technique is useful for substring problems
• Consider efficiency when working with strings, especially with concatenation operations

Understanding these standard string algorithms gives you a foundation for solving a wide range of text processing problems. By adapting and combining these techniques, you can develop custom algorithms for specific string manipulation needs.