इस स्ट्रिंग मैनिपुलेशन कोड की स्पेस जटिलता क्या है?

Question

कोड का यह टुकड़ा कोडिंग साक्षात्कार पुस्तक को क्रैकिंग से है।

public static boolean isUniqueChars2(String str) { 
    boolean[] char_set = new boolean[256]; 
    for (int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i); 
     if (char_set[val]) return false; 
     char_set[val] = true; 
    } 
    return true; 
} 

और लेखक कहा गया है कि,

समय जटिलता हे (एन), जहां n स्ट्रिंग की लंबाई है, और अंतरिक्ष जटिलता हे (एन) है।

मैं समझता हूँ कि समय जटिलता हे किया जा रहा है (एन) लेकिन मुझे समझ नहीं आता कि कैसे अंतरिक्ष जटिलता हे हो सकता है (एन)

मेरे सोच: char_set आकार 256 की एक सरणी कोई बात नहीं क्या रहेगा इनपुट (str) आकार है। भले ही "str" ​​की लंबाई 100,000 है, char_set अभी भी एक 256 तत्व सरणी है। तो मैंने सोचा, चूंकि इस फ़ंक्शन के लिए मेमोरी आवश्यकता इनपुट के आकार के साथ नहीं बदलती है और निरंतर 256 रहती है, इसलिए अंतरिक्ष जटिलता निरंतर है, यानी, ओ (1)।

किसी को, व्याख्या कर सकते हैं अगर मैं गलत हूँ (और, क्यों?)

बहुत बहुत शुक्रिया।

Answer 1

यह थोड़ा और अधिक जटिल है, मुझे लगता है कि:

पुनरावृत्तियों की अधिकतम संख्या से पहले कुछ चरित्र दो बार का सामना करना पड़ा हो जाएगा वर्णमाला स्ट्रिंग के ऊपर बना हुआ है का आकार है।

यदि यह आकार सीमित है, तो समय जटिलता ओ (1) है, यदि यह नहीं है, तो बूलियन सरणी परिमित आकार का नहीं हो सकता है, इस प्रकार, अंतरिक्ष जटिलता ओ (एन) होगी।