<jupyter_start><jupyter_text>Q1.3 URLifyReplace all spaces in string s with '%20'Input: string sReturn: modified string s<jupyter_code># 1. python replace

def URLify1(s):
    """
    space O(n)   create a new string
    time O(n)
    """
    return s.replace(' ', '%20')
# 2. inplace

def URLify2(s):
    """
    assume s is a char array, pad spaces, and traverse from last to first, use two pointers to fill
    - one pointer for real string
    - one pointer for padded string
    
    space O(1)  here we use char array to simulate a mutable string
    time O(n)
    """
    
    char_arr = [c for c in s]
    n = len(s)
    
    # count spaces
    spaces = 0
    for c in char_arr:
        if c == ' ':
            spaces += 1
        
    # pad required spaces to array
    space_to_pad = spaces*2
    for i in range(space_to_pad):
        char_arr.append(' ')
    
    # back traverse the array to fill '%20' inplace
    i = n-1             # true last idx
    j = len(char_arr)-1 # padded last idx
    
    while i < j and i >= 0:
        if char_arr[i] != ' ':
            # fill idx j with char_arr[i], both move 1 space left
            char_arr[j] = char_arr[i]
            j -= 1
            i -= 1
        else:
            char_arr[(j-2):(j+1)] = ['%','2','0']
            j -= 3
            i -= 1
            
    return ''.join(char_arr)

# Testcases

def URLify(s1):
    return URLify2(s1)

s1 = ""
s2 = "a d e"
s22 = "a%20d%20e"
s3 = "abd"
s33 = "abd"
print(URLify(s1) == s1)
print(URLify(s2) == s22)
print(URLify(s3) == s33)<jupyter_output>True
True
True
{'fraction_non_alphanumeric': 0.12253968253968255, 'fraction_numerical': 0.031746031746031744, 'mean_word_length': 1.8970588235294117, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '646359', 'license': 'MIT', 'n_tokens_mistral': 595, 'n_tokens_neox': 569, 'n_words': 184, 'path': 'CCI/Ch1_Arrays_and_Strings/Q3_URLify.ipynb', 'repo_name': 'alice-yang94/coding-interview-prep', 'size': '1575'}