String Validation

Overview

String validation involves checking if a string meets specific criteria, patterns, or constraints. Validation is crucial for data integrity, security, and user input verification. String validation problems test your understanding of regular expressions, state machines, parsing, and pattern matching.

Common validation problems include:

• Valid parentheses/brackets
• Valid email/URL/phone number
• Valid number formats
• Valid password strength
• Valid IP address
• Valid date/time formats
• Pattern matching validation

Pattern 1: Valid Parentheses

Check if parentheses are properly matched and nested.

Basic parentheses:

function isValidParentheses(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (const char of s) {
    if (pairs[char]) {
      // Closing bracket
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    } else if (char === '(' || char === '{' || char === '[') {
      // Opening bracket
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

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

Optimized with counter (single type):

function isValidSingleType(s: string): boolean {
  let count = 0;
  
  for (const char of s) {
    if (char === '(') {
      count++;
    } else if (char === ')') {
      count--;
      if (count < 0) return false;
    }
  }
  
  return count === 0;
}

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

Pattern 2: Valid Number

Validate if a string represents a valid number.

Valid integer/decimal/scientific notation:

function isValidNumber(s: string): boolean {
  let i = 0;
  const n = s.length;
  
  // Skip leading whitespace
  while (i < n && s[i] === ' ') i++;
  
  // Optional sign
  if (i < n && (s[i] === '+' || s[i] === '-')) i++;
  
  let hasDigits = false;
  let hasDot = false;
  
  // Parse integer part
  while (i < n && s[i] >= '0' && s[i] <= '9') {
    hasDigits = true;
    i++;
  }
  
  // Optional decimal point
  if (i < n && s[i] === '.') {
    hasDot = true;
    i++;
    while (i < n && s[i] >= '0' && s[i] <= '9') {
      hasDigits = true;
      i++;
    }
  }
  
  // Must have at least one digit
  if (!hasDigits) return false;
  
  // Optional exponent
  if (i < n && (s[i] === 'e' || s[i] === 'E')) {
    i++;
    if (i < n && (s[i] === '+' || s[i] === '-')) i++;
    let expDigits = false;
    while (i < n && s[i] >= '0' && s[i] <= '9') {
      expDigits = true;
      i++;
    }
    if (!expDigits) return false;
  }
  
  // Skip trailing whitespace
  while (i < n && s[i] === ' ') i++;
  
  return i === n;
}

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

Valid integer only:

function isValidInteger(s: string): boolean {
  s = s.trim();
  if (s.length === 0) return false;
  
  let i = 0;
  if (s[i] === '+' || s[i] === '-') i++;
  
  if (i >= s.length) return false;
  
  while (i < s.length) {
    if (s[i] < '0' || s[i] > '9') return false;
    i++;
  }
  
  return true;
}

Pattern 3: Valid Email Address

Validate email address format.

function isValidEmail(email: string): boolean {
  const parts = email.split('@');
  if (parts.length !== 2) return false;
  
  const [local, domain] = parts;
  
  // Validate local part
  if (local.length === 0 || local.length > 64) return false;
  if (local[0] === '.' || local[local.length - 1] === '.') return false;
  if (local.includes('..')) return false;
  
  for (const char of local) {
    if (!/[a-zA-Z0-9._+-]/.test(char)) return false;
  }
  
  // Validate domain part
  if (domain.length === 0 || domain.length > 255) return false;
  const domainParts = domain.split('.');
  if (domainParts.length < 2) return false;
  
  for (const part of domainParts) {
    if (part.length === 0 || part.length > 63) return false;
    if (part[0] === '-' || part[part.length - 1] === '-') return false;
    for (const char of part) {
      if (!/[a-zA-Z0-9-]/.test(char)) return false;
    }
  }
  
  return true;
}

Simplified regex version:

function isValidEmailRegex(email: string): boolean {
  const emailRegex = /^[a-zA-Z0-9._+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$/;
  return emailRegex.test(email);
}

Pattern 4: Valid URL

Validate URL format.

function isValidURL(url: string): boolean {
  try {
    const urlObj = new URL(url);
    return urlObj.protocol === 'http:' || urlObj.protocol === 'https:';
  } catch {
    return false;
  }
}

Manual validation:

function isValidURLManual(url: string): boolean {
  // Check protocol
  if (!url.startsWith('http://') && !url.startsWith('https://')) {
    return false;
  }
  
  // Remove protocol
  const withoutProtocol = url.replace(/^https?:\/\//, '');
  if (withoutProtocol.length === 0) return false;
  
  // Split domain and path
  const parts = withoutProtocol.split('/');
  const domain = parts[0];
  
  // Validate domain
  if (domain.length === 0 || domain.length > 253) return false;
  const domainParts = domain.split('.');
  if (domainParts.length < 2) return false;
  
  for (const part of domainParts) {
    if (part.length === 0 || part.length > 63) return false;
    if (!/^[a-zA-Z0-9][a-zA-Z0-9-]*[a-zA-Z0-9]$|^[a-zA-Z0-9]$/.test(part)) {
      return false;
    }
  }
  
  return true;
}

Pattern 5: Valid IP Address

Validate IPv4 or IPv6 address.

IPv4 validation:

function isValidIPv4(ip: string): boolean {
  const parts = ip.split('.');
  if (parts.length !== 4) return false;
  
  for (const part of parts) {
    const num = parseInt(part, 10);
    if (isNaN(num) || num < 0 || num > 255) return false;
    if (part.length > 1 && part[0] === '0') return false; // No leading zeros
    if (part !== num.toString()) return false; // No extra characters
  }
  
  return true;
}

IPv6 validation:

function isValidIPv6(ip: string): boolean {
  const parts = ip.split(':');
  if (parts.length < 2 || parts.length > 8) return false;
  
  let emptyCount = 0;
  for (const part of parts) {
    if (part === '') {
      emptyCount++;
      if (emptyCount > 1) return false;
      continue;
    }
    
    if (part.length > 4) return false;
    
    for (const char of part) {
      if (!/[0-9a-fA-F]/.test(char)) return false;
    }
  }
  
  return true;
}

Pattern 6: Valid Password

Validate password strength and requirements.

interface PasswordRules {
  minLength?: number;
  maxLength?: number;
  requireUppercase?: boolean;
  requireLowercase?: boolean;
  requireDigit?: boolean;
  requireSpecial?: boolean;
  specialChars?: string;
}

function isValidPassword(password: string, rules: PasswordRules): boolean {
  const {
    minLength = 8,
    maxLength = Infinity,
    requireUppercase = false,
    requireLowercase = false,
    requireDigit = false,
    requireSpecial = false,
    specialChars = '!@#$%^&*'
  } = rules;
  
  if (password.length < minLength || password.length > maxLength) {
    return false;
  }
  
  if (requireUppercase && !/[A-Z]/.test(password)) {
    return false;
  }
  
  if (requireLowercase && !/[a-z]/.test(password)) {
    return false;
  }
  
  if (requireDigit && !/[0-9]/.test(password)) {
    return false;
  }
  
  if (requireSpecial) {
    const specialRegex = new RegExp(`[${specialChars.replace(/[.*+?^${}()|[\]\\]/g, '\\$&')}]`);
    if (!specialRegex.test(password)) {
      return false;
    }
  }
  
  return true;
}

Check password strength:

function getPasswordStrength(password: string): 'weak' | 'medium' | 'strong' {
  let score = 0;
  
  if (password.length >= 8) score++;
  if (password.length >= 12) score++;
  if (/[a-z]/.test(password)) score++;
  if (/[A-Z]/.test(password)) score++;
  if (/[0-9]/.test(password)) score++;
  if (/[^a-zA-Z0-9]/.test(password)) score++;
  
  if (score <= 2) return 'weak';
  if (score <= 4) return 'medium';
  return 'strong';
}

Pattern 7: Valid Phone Number

Validate phone number formats.

US phone number:

function isValidUSPhone(phone: string): boolean {
  // Remove formatting
  const cleaned = phone.replace(/[\s()-]/g, '');
  
  // Check format: (XXX) XXX-XXXX or XXX-XXX-XXXX
  const regex = /^(\d{3})?\d{3}\d{4}$/;
  return regex.test(cleaned) && cleaned.length >= 10 && cleaned.length <= 11;
}

International format:

function isValidInternationalPhone(phone: string): boolean {
  // Remove formatting
  const cleaned = phone.replace(/[\s()-]/g, '');
  
  // Must start with + and have 10-15 digits
  if (!cleaned.startsWith('+')) return false;
  
  const digits = cleaned.substring(1);
  if (digits.length < 10 || digits.length > 15) return false;
  
  return /^\d+$/.test(digits);
}

Pattern 8: Valid Date/Time Format

Validate date and time formats.

Date validation (YYYY-MM-DD):

function isValidDate(dateStr: string): boolean {
  const parts = dateStr.split('-');
  if (parts.length !== 3) return false;
  
  const year = parseInt(parts[0], 10);
  const month = parseInt(parts[1], 10);
  const day = parseInt(parts[2], 10);
  
  if (isNaN(year) || isNaN(month) || isNaN(day)) return false;
  if (month < 1 || month > 12) return false;
  if (day < 1 || day > 31) return false;
  
  const date = new Date(year, month - 1, day);
  return date.getFullYear() === year &&
         date.getMonth() === month - 1 &&
         date.getDate() === day;
}

Time validation (HH:MM:SS):

function isValidTime(timeStr: string): boolean {
  const parts = timeStr.split(':');
  if (parts.length !== 3) return false;
  
  const hour = parseInt(parts[0], 10);
  const minute = parseInt(parts[1], 10);
  const second = parseInt(parts[2], 10);
  
  if (isNaN(hour) || isNaN(minute) || isNaN(second)) return false;
  
  return hour >= 0 && hour < 24 &&
         minute >= 0 && minute < 60 &&
         second >= 0 && second < 60;
}

Pattern 9: Valid Pattern Matching

Validate if string matches a specific pattern.

Wildcard pattern matching:

function isValidWildcard(s: string, pattern: string): boolean {
  const dp: boolean[][] = Array(s.length + 1)
    .fill(null)
    .map(() => Array(pattern.length + 1).fill(false));
  
  dp[0][0] = true;
  
  // Handle patterns starting with *
  for (let j = 1; j <= pattern.length && pattern[j - 1] === '*'; j++) {
    dp[0][j] = true;
  }
  
  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= pattern.length; j++) {
      if (pattern[j - 1] === '*') {
        dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
      } else if (pattern[j - 1] === '?' || pattern[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  
  return dp[s.length][pattern.length];
}

Regex pattern matching:

function matchesPattern(s: string, pattern: string): boolean {
  try {
    const regex = new RegExp(`^${pattern}$`);
    return regex.test(s);
  } catch {
    return false;
  }
}

Pattern 10: Valid String Constraints

Validate string against multiple constraints.

Length constraints:

function isValidLength(s: string, min: number, max: number): boolean {
  return s.length >= min && s.length <= max;
}

Character set constraints:

function isValidCharacterSet(s: string, allowedChars: string | RegExp): boolean {
  const regex = typeof allowedChars === 'string' 
    ? new RegExp(`^[${allowedChars.replace(/[.*+?^${}()|[\]\\]/g, '\\$&')}]*$`)
    : allowedChars;
  return regex.test(s);
}

No consecutive duplicates:

function hasNoConsecutiveDuplicates(s: string): boolean {
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) return false;
  }
  return true;
}

Unique characters only:

function hasUniqueCharacters(s: string): boolean {
  const seen = new Set<string>();
  for (const char of s) {
    if (seen.has(char)) return false;
    seen.add(char);
  }
  return true;
}

Pattern 11: Valid String Format

Validate specific string formats.

Valid identifier (variable name):

function isValidIdentifier(s: string): boolean {
  if (s.length === 0) return false;
  if (!/[a-zA-Z_]/.test(s[0])) return false;
  
  for (let i = 1; i < s.length; i++) {
    if (!/[a-zA-Z0-9_]/.test(s[i])) return false;
  }
  
  return true;
}

Valid hex color:

function isValidHexColor(color: string): boolean {
  return /^#([0-9A-Fa-f]{3}|[0-9A-Fa-f]{6})$/.test(color);
}

Valid credit card (Luhn algorithm):

function isValidCreditCard(cardNumber: string): boolean {
  const digits = cardNumber.replace(/\s/g, '');
  if (!/^\d{13,19}$/.test(digits)) return false;
  
  let sum = 0;
  let isEven = false;
  
  for (let i = digits.length - 1; i >= 0; i--) {
    let digit = parseInt(digits[i], 10);
    
    if (isEven) {
      digit *= 2;
      if (digit > 9) digit -= 9;
    }
    
    sum += digit;
    isEven = !isEven;
  }
  
  return sum % 10 === 0;
}

Pattern 12: Valid String Structure

Validate hierarchical or structured strings.

Valid XML-like tags:

function isValidTags(s: string): boolean {
  const stack: string[] = [];
  let i = 0;
  
  while (i < s.length) {
    if (s[i] === '<') {
      const end = s.indexOf('>', i);
      if (end === -1) return false;
      
      const tag = s.substring(i + 1, end);
      
      if (tag.startsWith('/')) {
        // Closing tag
        const tagName = tag.substring(1);
        if (stack.length === 0 || stack.pop() !== tagName) {
          return false;
        }
      } else {
        // Opening tag
        if (!/^[a-zA-Z][a-zA-Z0-9]*$/.test(tag)) return false;
        stack.push(tag);
      }
      
      i = end + 1;
    } else {
      i++;
    }
  }
  
  return stack.length === 0;
}

Valid JSON structure (simplified):

function isValidJSONStructure(s: string): boolean {
  try {
    JSON.parse(s);
    return true;
  } catch {
    return false;
  }
}

When to Use String Validation

Use validation techniques when:

• Problem asks about "valid", "validate", or "check"
• Need to verify format or pattern
• Input validation is required
• Data integrity checks
• Security validation (passwords, emails)
• Format compliance (dates, numbers, URLs)

Template (Basic Validation)

function validateTemplate(s: string, rules: ValidationRule[]): boolean {
  for (const rule of rules) {
    if (!rule(s)) return false;
  }
  return true;
}

type ValidationRule = (s: string) => boolean;

Template (State Machine Validation)

function validateStateMachine(s: string, transitions: Map<string, (char: string) => string>): boolean {
  let state = 'start';
  
  for (const char of s) {
    const transition = transitions.get(state);
    if (!transition) return false;
    
    state = transition(char);
    if (state === 'error') return false;
  }
  
  return state === 'accept';
}

Time and Space Complexity Summary

• Parentheses validation: O(n) time, O(n) space (stack), O(1) space (counter)
• Number validation: O(n) time, O(1) space
• Email/URL validation: O(n) time, O(1) space
• Pattern matching: O(n * m) time for wildcard, O(n) for regex
• Password validation: O(n) time, O(1) space

Practice Tips

1. Use regex carefully — Understand performance implications
2. Handle edge cases — Empty strings, null, special characters
3. Consider state machines — For complex validation rules
4. Optimize early returns — Fail fast for invalid input
5. Test thoroughly — Cover all edge cases and boundary conditions
6. Use built-in validators — When available (URL, Date constructors)

Common Mistakes

1. Not handling empty strings — Always check length first
2. Regex complexity — Keep regex patterns simple and readable
3. Case sensitivity — Be consistent with case handling
4. Whitespace handling — Trim or preserve as needed
5. Unicode handling — Consider multi-byte characters

Related Concepts

• Regular Expressions — Pattern matching for validation
• State Machines — Complex validation logic
• String Parsing — Parsing and validating simultaneously
• Character Counting — Frequency-based validation

String validation is essential for data integrity and security. Master these patterns, and you'll be well-prepared for validation-related interview questions.