String Transformation

Overview

String transformation involves converting a string from one form to another through various operations like case conversion, character mapping, encoding, decoding, and pattern-based transformations. Transformation problems test your understanding of string manipulation, character encoding, and efficient conversion techniques.

Common transformation problems include:

• Case conversion (upper/lower/title case)
• Character mapping and substitution
• Encoding/decoding (Base64, URL encoding)
• String normalization
• Pattern-based transformations
• Character shifting (Caesar cipher)
• String formatting and padding

Pattern 1: Case Conversion

Convert string between different case formats.

To lowercase:

function toLowerCase(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char >= 'A' && char <= 'Z') {
      result.push(String.fromCharCode(char.charCodeAt(0) + 32));
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

To uppercase:

function toUpperCase(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char >= 'a' && char <= 'z') {
      result.push(String.fromCharCode(char.charCodeAt(0) - 32));
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Toggle case:

function toggleCase(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char >= 'A' && char <= 'Z') {
      result.push(String.fromCharCode(char.charCodeAt(0) + 32));
    } else if (char >= 'a' && char <= 'z') {
      result.push(String.fromCharCode(char.charCodeAt(0) - 32));
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Title case (capitalize first letter of each word):

function toTitleCase(s: string): string {
  const words = s.toLowerCase().split(/\s+/);
  
  return words.map(word => {
    if (word.length === 0) return word;
    return word[0].toUpperCase() + word.substring(1);
  }).join(' ');
}

Time: O(n), Space: O(n)

Pattern 2: Character Mapping and Substitution

Replace characters based on mapping rules.

Simple character mapping:

function mapCharacters(s: string, mapping: Map<string, string>): string {
  const result: string[] = [];
  
  for (const char of s) {
    result.push(mapping.get(char) || char);
  }
  
  return result.join('');
}

Character substitution with function:

function transformCharacters(s: string, transform: (char: string) => string): string {
  const result: string[] = [];
  
  for (const char of s) {
    result.push(transform(char));
  }
  
  return result.join('');
}

Replace all occurrences:

function replaceAll(s: string, oldChar: string, newChar: string): string {
  return s.split(oldChar).join(newChar);
}

Replace using regex:

function replacePattern(s: string, pattern: RegExp, replacement: string): string {
  return s.replace(pattern, replacement);
}

Pattern 3: Character Shifting (Caesar Cipher)

Shift characters by a fixed amount in the alphabet.

Caesar cipher (shift by k positions):

function caesarCipher(s: string, shift: number): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char >= 'a' && char <= 'z') {
      const shifted = ((char.charCodeAt(0) - 'a'.charCodeAt(0) + shift) % 26 + 26) % 26;
      result.push(String.fromCharCode(shifted + 'a'.charCodeAt(0)));
    } else if (char >= 'A' && char <= 'Z') {
      const shifted = ((char.charCodeAt(0) - 'A'.charCodeAt(0) + shift) % 26 + 26) % 26;
      result.push(String.fromCharCode(shifted + 'A'.charCodeAt(0)));
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Example: "abc" with shift=3 → "def"

Time: O(n), Space: O(n)

Decode Caesar cipher:

function decodeCaesar(s: string, shift: number): string {
  return caesarCipher(s, -shift);
}

Pattern 4: String Normalization

Normalize string to a standard form.

Remove extra spaces:

function normalizeSpaces(s: string): string {
  return s.trim().replace(/\s+/g, ' ');
}

Normalize line endings:

function normalizeLineEndings(s: string): string {
  return s.replace(/\r\n/g, '\n').replace(/\r/g, '\n');
}

Remove diacritics (accents):

function removeDiacritics(s: string): string {
  return s.normalize('NFD').replace(/[\u0300-\u036f]/g, '');
}

Normalize Unicode:

function normalizeUnicode(s: string, form: 'NFC' | 'NFD' | 'NFKC' | 'NFKD' = 'NFC'): string {
  return s.normalize(form);
}

Pattern 5: String Encoding/Decoding

Encode and decode strings using various formats.

URL encoding:

function urlEncode(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (/[a-zA-Z0-9-._~]/.test(char)) {
      result.push(char);
    } else {
      const code = char.charCodeAt(0);
      if (code < 256) {
        result.push(`%${code.toString(16).toUpperCase().padStart(2, '0')}`);
      } else {
        // UTF-8 encoding for multi-byte characters
        const bytes = encodeUTF8(char);
        for (const byte of bytes) {
          result.push(`%${byte.toString(16).toUpperCase().padStart(2, '0')}`);
        }
      }
    }
  }
  
  return result.join('');
}

function encodeUTF8(char: string): number[] {
  const code = char.charCodeAt(0);
  if (code < 0x80) return [code];
  if (code < 0x800) return [0xC0 | (code >> 6), 0x80 | (code & 0x3F)];
  return [0xE0 | (code >> 12), 0x80 | ((code >> 6) & 0x3F), 0x80 | (code & 0x3F)];
}

URL decoding:

function urlDecode(s: string): string {
  const result: string[] = [];
  let i = 0;
  
  while (i < s.length) {
    if (s[i] === '%' && i + 2 < s.length) {
      const hex = s.substring(i + 1, i + 3);
      const code = parseInt(hex, 16);
      result.push(String.fromCharCode(code));
      i += 3;
    } else {
      result.push(s[i++]);
    }
  }
  
  return result.join('');
}

Base64-like encoding (simplified):

function base64Encode(s: string): string {
  const base64 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';
  const bytes: number[] = [];
  
  for (const char of s) {
    const code = char.charCodeAt(0);
    bytes.push(code >> 8, code & 0xFF);
  }
  
  const result: string[] = [];
  for (let i = 0; i < bytes.length; i += 3) {
    const b1 = bytes[i] || 0;
    const b2 = bytes[i + 1] || 0;
    const b3 = bytes[i + 2] || 0;
    
    const bitmap = (b1 << 16) | (b2 << 8) | b3;
    
    result.push(base64[(bitmap >> 18) & 63]);
    result.push(base64[(bitmap >> 12) & 63]);
    result.push(i + 1 < bytes.length ? base64[(bitmap >> 6) & 63] : '=');
    result.push(i + 2 < bytes.length ? base64[bitmap & 63] : '=');
  }
  
  return result.join('');
}

Pattern 6: String Padding and Truncation

Add or remove characters to achieve desired length.

Pad left:

function padLeft(s: string, length: number, padChar: string = ' '): string {
  if (s.length >= length) return s;
  return padChar.repeat(length - s.length) + s;
}

Pad right:

function padRight(s: string, length: number, padChar: string = ' '): string {
  if (s.length >= length) return s;
  return s + padChar.repeat(length - s.length);
}

Pad center:

function padCenter(s: string, length: number, padChar: string = ' '): string {
  if (s.length >= length) return s;
  
  const totalPadding = length - s.length;
  const leftPadding = Math.floor(totalPadding / 2);
  const rightPadding = totalPadding - leftPadding;
  
  return padChar.repeat(leftPadding) + s + padChar.repeat(rightPadding);
}

Truncate with ellipsis:

function truncate(s: string, maxLength: number, ellipsis: string = '...'): string {
  if (s.length <= maxLength) return s;
  return s.substring(0, maxLength - ellipsis.length) + ellipsis;
}

Pattern 7: String Formatting

Format string with placeholders or templates.

Simple placeholder replacement:

function formatString(template: string, values: Record<string, string>): string {
  return template.replace(/\{\{([^}]+)\}\}/g, (match, key) => {
    return values[key.trim()] || match;
  });
}

Example: formatString("Hello {{name}}", {name: "World"}) → "Hello World"

Format with positional arguments:

function formatPositional(template: string, ...args: string[]): string {
  return template.replace(/\{(\d+)\}/g, (match, index) => {
    const idx = parseInt(index, 10);
    return args[idx] !== undefined ? args[idx] : match;
  });
}

Example: formatPositional("{0} {1} {0}", "Hello", "World") → "Hello World Hello"

Pattern 8: Character Frequency Transformation

Transform string based on character frequencies.

Sort by frequency:

function sortByFrequency(s: string): string {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const sorted = Array.from(s).sort((a, b) => {
    const freqA = freq.get(a)!;
    const freqB = freq.get(b)!;
    if (freqB !== freqA) {
      return freqB - freqA; // Higher frequency first
    }
    return a.localeCompare(b); // Then alphabetically
  });
  
  return sorted.join('');
}

Transform based on frequency threshold:

function transformByFrequency(s: string, threshold: number, transform: (char: string) => string): string {
  const freq = new Map<string, number>();
  
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  const result: string[] = [];
  for (const char of s) {
    if (freq.get(char)! >= threshold) {
      result.push(transform(char));
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Pattern 9: Pattern-Based Transformation

Transform string based on patterns or rules.

Transform alternating characters:

function transformAlternating(s: string, transform1: (char: string) => string, transform2: (char: string) => string): string {
  const result: string[] = [];
  
  for (let i = 0; i < s.length; i++) {
    if (i % 2 === 0) {
      result.push(transform1(s[i]));
    } else {
      result.push(transform2(s[i]));
    }
  }
  
  return result.join('');
}

Transform based on position:

function transformByPosition(s: string, transform: (char: string, index: number) => string): string {
  const result: string[] = [];
  
  for (let i = 0; i < s.length; i++) {
    result.push(transform(s[i], i));
  }
  
  return result.join('');
}

Transform based on adjacent characters:

function transformByAdjacent(s: string, transform: (char: string, prev: string | null, next: string | null) => string): string {
  const result: string[] = [];
  
  for (let i = 0; i < s.length; i++) {
    const prev = i > 0 ? s[i - 1] : null;
    const next = i < s.length - 1 ? s[i + 1] : null;
    result.push(transform(s[i], prev, next));
  }
  
  return result.join('');
}

Pattern 10: String Interpolation

Insert values into string templates.

Simple interpolation:

function interpolate(template: string, values: Record<string, any>): string {
  return template.replace(/\$\{([^}]+)\}/g, (match, key) => {
    return values[key] !== undefined ? String(values[key]) : match;
  });
}

Example: interpolate("Hello ${name}", {name: "World"}) → "Hello World"

Interpolation with default values:

function interpolateWithDefault(template: string, values: Record<string, any>, defaultValue: string = ''): string {
  return template.replace(/\$\{([^}]+)\}/g, (match, key) => {
    return values[key] !== undefined ? String(values[key]) : defaultValue;
  });
}

Pattern 11: String Sanitization

Clean and sanitize strings for safe use.

Remove special characters:

function removeSpecialChars(s: string): string {
  return s.replace(/[^a-zA-Z0-9\s]/g, '');
}

Escape HTML:

function escapeHtml(s: string): string {
  const map: Record<string, string> = {
    '&': '&amp;',
    '<': '&lt;',
    '>': '&gt;',
    '"': '&quot;',
    "'": '&#039;'
  };
  
  return s.replace(/[&<>"']/g, char => map[char]);
}

Sanitize filename:

function sanitizeFilename(filename: string): string {
  return filename.replace(/[^a-zA-Z0-9._-]/g, '_').replace(/\.{2,}/g, '.');
}

Remove control characters:

function removeControlChars(s: string): string {
  return s.replace(/[\x00-\x1F\x7F]/g, '');
}

Pattern 12: String Expansion

Expand compressed or encoded strings.

Expand character ranges:

function expandRange(s: string): string {
  return s.replace(/([a-z])-([a-z])/gi, (match, start, end) => {
    const startCode = start.charCodeAt(0);
    const endCode = end.charCodeAt(0);
    const result: string[] = [];
    
    for (let i = startCode; i <= endCode; i++) {
      result.push(String.fromCharCode(i));
    }
    
    return result.join('');
  });
}

Example: "a-c" → "abc"

Expand numeric ranges:

function expandNumericRange(s: string): string {
  return s.replace(/(\d+)-(\d+)/g, (match, start, end) => {
    const startNum = parseInt(start, 10);
    const endNum = parseInt(end, 10);
    const result: string[] = [];
    
    for (let i = startNum; i <= endNum; i++) {
      result.push(i.toString());
    }
    
    return result.join(',');
  });
}

Example: "1-3" → "1,2,3"

When to Use String Transformation

Use transformation techniques when:

• Problem asks about "transform", "convert", "encode", or "format"
• Need to change case or character encoding
• Sanitizing or normalizing strings
• Formatting strings with templates
• Encoding/decoding for transmission or storage
• Pattern-based character modifications

Template (Character Transformation)

function transformTemplate(s: string, transform: (char: string) => string): string {
  const result: string[] = [];
  
  for (const char of s) {
    result.push(transform(char));
  }
  
  return result.join('');
}

Template (Conditional Transformation)

function conditionalTransformTemplate(s: string, condition: (char: string) => boolean, transform: (char: string) => string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (condition(char)) {
      result.push(transform(char));
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Time and Space Complexity Summary

• Case conversion: O(n) time, O(n) space
• Character mapping: O(n) time, O(n) space
• Caesar cipher: O(n) time, O(n) space
• Encoding/decoding: O(n) time, O(n) space
• Padding/truncation: O(n) time, O(n) space
• Formatting: O(n) time, O(n) space

Practice Tips

1. Use character codes — Efficient for case conversion and shifting
2. Handle Unicode — Consider multi-byte characters
3. Preserve structure — Maintain spaces, formatting when needed
4. Validate input — Check for edge cases
5. Optimize loops — Use array methods or manual loops efficiently
6. Consider encoding — Understand character encoding implications

Common Mistakes

1. Case sensitivity — Be consistent with case handling
2. Unicode handling — Multi-byte characters need special care
3. Encoding issues — Understand UTF-8, ASCII differences
4. Off-by-one errors — Character code calculations
5. Not preserving structure — Losing spaces or formatting

Related Concepts

• String Manipulation — Core operations for transformation
• Character Encoding — Understanding character representations
• Regular Expressions — Pattern matching for transformations
• Character Counting — Frequency-based transformations

String transformation is essential for data processing, formatting, and encoding tasks. Master these patterns, and you'll be well-prepared for transformation-related interview questions.