šŸ“…Day-12 Striver’s SDE Sheet | Arrays Part 4 | Count number of subarrays with given xor K , Longest Substring without repeat.

Payal KumariPayal Kumari
8 min read

Note : Started my 27-day DSA journey with Striver’s SDE Sheet!
I will be journaling every day — recording what I learn, reflecting on it, and sharing it with my network to help fellow learners and aspiring developers.. Learning through videos, resources, and the internet — simplifying logic in my own way with real-world connections. Sharing 2 questions daily: brute-force to optimal, clean Java code, time & space complexity, and key patterns.

This blog series is for anyone preparing for coding interviews — whether you’re a beginner or a revision warrior. Let’s grow together! šŸš€

Namaste Developers! šŸ™

Welcome to Day 12 of my 27-day DSA journey using Striver’s SDE Sheet!

1ļøāƒ£ Count number of subarrays with given xor K

šŸ”ø Problem Statement:

Given an array of integers A and an integer B. Find the total number of subarrays having bitwise XOR of all elements equal to k.


Example 1:
Input Format: A = [4, 2, 2, 6, 4] , k = 6
Result: 4
Explanation: The subarrays having XOR of their elements as 6 are  [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]

Example 2:
Input Format: A = [5, 6, 7, 8, 9], k = 5
Result: 2
Explanation: The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]

šŸ’ Real World Example

XOR ka matlab hota hai exclusive OR — jisme bits alag ho tabhi result 1 hota hai.

Input AInput BOutput
000
011
101
110
  • Think of XOR like this:-

    āœ… Suppose you and your friend both have different ideas, toh combined result exciting hoga (1).

    āœ… But if you both think the same (0,0 or 1,1), toh result boring hoga (0).

(Hinglish : XOR ko aise socho:
Agar tum aur tumhara friend dono ke ideas alag-alag hain, toh jo result aayega wo exciting hoga (1).
Lekin agar dono same soch rahe ho (jaise 0-0 ya 1-1), toh result boring hoga (0).)

šŸ’ Brute Force Approach – TLE Risk but Concept Clear

šŸ“Idea:

  • Check every subarray.

  • Calculate XOR of all elements.

  • Count if XOR == k.

class Solution {
    public long subarrayXor(int arr[], int k) {
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        int xor = 0;
        for (int j = i; j < arr.length; j++) {
            xor ^= arr[j];
            if (xor == k) count++;
        }
    }
    return count;
  }

}

šŸ“Time Complexity (TC):

  • O(n²) — because of nested loop

šŸ“ Space Complexity (SC):

  • O(1) — no extra space used

āš ļø Note:

Brute force TLE de sakta hai jab input bada ho, like 10^5 size array!

šŸ’ Optimal Approach – HashMap with XOR Concept

šŸ“Intuition:

Let’s say we calculate prefix XOR till index i:

  • Let xor = prefix XOR till index i

  • Then, we check:
    If (xor ^ k) already occurred before,
    then there exists a subarray whose XOR = k.

XOR property used:

If A ^ B = C, then A = B ^ C and B = A ^ C

So, we use a HashMap to store frequency of prefix XORs.

class Solution {
    public long subarrayXor(int arr[], int k) {
     Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        int xor = 0;

        for (int i = 0; i < arr.length; i++) {
            xor ^= arr[i];

            if (xor == k) count++;

            int required = xor ^ k;
            count += map.getOrDefault(required, 0);

            map.put(xor, map.getOrDefault(xor, 0) + 1);
        }

        return count;
      }

    }

āœ… Step-by-step Dry Run:

IndexNumxor (prefix XOR)xor ^ k = neededMap LookupAdd to CountUpdated MapTotal Count
040 ^ 4 = 44 ^ 6 = 2āŒ (not found)āŒ{4: 1}0
124 ^ 2 = 66 ^ 6 = 0āŒāœ… xor == k{4:1, 6:1}1
226 ^ 2 = 44 ^ 6 = 2āŒāŒ{4:2, 6:1}1
364 ^ 6 = 22 ^ 6 = 4āœ… found 4 → map[4]=2āœ… +2 subarrays{4:2, 6:1, 2:1}3
442 ^ 4 = 66 ^ 6 = 0āŒāœ… xor == k{4:2, 6:2, 2:1}4

āœ… Final Count = 4

šŸ“Time Complexity:

  • O(n) — one traversal

šŸ“Space Complexity:

  • O(n) — for HashMap

šŸ’ Real World Application

  • Network Security – XOR used in encryption (e.g. stream ciphers)

  • Bit Manipulation Problems – Used in leetcode, CP (competitive programming)

  • Debugging – Finding unique elements, prefix sums with twist

(Tips Hinglish :

  • ā€œPrefix XORā€ ka idea samajhna zaroori hai — har index tak ka XOR calculate karna.

  • ā€œxor ^ kā€ = required value jo map mein search karni hai.

  • HashMap frequency store karne ke kaam aata hai — bina dikhaye kaam karta hai background mein)


2ļøāƒ£ Longest Substring Without Repeating Characters

šŸ”ø Problem Statement:

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

  • 0 <= s.length <= 5 * 10<sup>4</sup>

  • s consists of English letters, digits, symbols and spaces.

šŸ“Real World Example

Imagine you’re playing a memory game :

  • You have to keep selecting different cards (characters),

  • The moment you pick a duplicate card, your current streak ends.

  • You start a new streak from the next card.

Aisa hi kuch hum kar rahe hain is problem mein!

šŸ’ Brute Force Approach

šŸ“Idea:

  • Generate all substrings.

  • For each substring, check if all characters are unique.

class Solution {
    public int lengthOfLongestSubstring(String s) {
    int maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> set = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (set.contains(s.charAt(j))) break;
            set.add(s.charAt(j));
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    return maxLength;
   }

 }

šŸ“Time Complexity: O(n²)

šŸ“Space Complexity: O(n)

šŸ’ Optimal Approach – Sliding Window + HashSet

šŸ“Ideas:

  • Use two pointers (left and right) to create a window.

  • Move right pointer to include new characters.

  • If duplicate found, move left pointer to remove until no duplicates remain.

Set use karenge to track which characters are inside window.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0, maxLen = 0;

        while (right < s.length()) {
            char ch = s.charAt(right);

            if (!set.contains(ch)) {
                set.add(ch);
                maxLen = Math.max(maxLen, right - left + 1);
                right++;
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }

        return maxLen;
    }
}

šŸ“Time Complexity: O(n)

šŸ“Space Complexity: O(n)

šŸ’ Dry Run – s = "abcabcbb"

StepLeftRightCharSet ContentmaxLen
100a{a}1
201b{a, b}2
302c{a, b, c}3 āœ…
403aDuplicate → move left
513a{b, c, a}3
...Keep going
Final
āœ… Answer: maxLen = 3 for substring "abc"

(Hinglish Tips

  • Set ko samjho: it stores only unique elements. Duplicate mila toh remove karo left se.

  • Sliding window ka matlab hota hai ek range jise hum dynamically adjust karte hain.

  • Don’t memorize — understand the logic. Try dry runs manually.)


āœļø Final Notes:

If you're just starting your DSA journey like me, don't worry if you don’t get it perfect the first time.
Visualize → Dry Run → Optimize.
Stay consistent, and let’s crack every problem from brute to optimal! šŸ’Ŗ

šŸ™ Special Thanks

A heartfelt thank you to Rajvikraaditya Sir for creating and sharing such an incredible DSA resource with the community (takeuforward). Your structured approach has made DSA more accessible and less intimidating for thousands of learners like me.

If this helped you, do share it with your fellow DSA learners.
Comment with your doubts — I’d love to answer and grow together 🌱

āœļø Payal Kumari šŸ‘©ā€šŸ’»
My 27-Day DSA Journey with Striver’s Sheet! #dsawithpayal

0
Subscribe to my newsletter

Read articles from Payal Kumari directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

Payal Kumari
Payal Kumari

I'm a passionate full-stack developer with a strong foundation in the MERN stack—building and maintaining scalable web applications using React.js, Node.js, and Next.js. My journey in open source began with Hacktoberfest 2023, where I made four impactful pull requests that sparked a love for collaborative coding, global learning, and open knowledge sharing. Since then, I’ve contributed to and mentored projects in top open source programs like GSSoC’24, SSOC’24, and C4GT’24. As a Google Gen AI Exchange Hackathon ’24 Finalist and Google’s Women Techmakers (WTM) Ambassador, I’ve been privileged to support diverse communities in building meaningful tech solutions. My work as a Top 50 Mentor for GSSoC ’24 reflects my commitment to nurturing new talent in tech. Beyond development, I serve as a Student Career Guide, Profile Building Expert & Evangelist at Topmate.io, where I conduct workshops, guide students through resume building and career strategy, and help mentees navigate open source and tech careers. Recognized among the Top 5% of mentors and featured on ā€œTopmate Discover,ā€ I take pride in making mentorship accessible and impactful. My technical voice has also been acknowledged by LinkedIn, where I’ve earned the Top Voice badge seven times in domains like web development, programming, and software engineering. In addition, I hold LinkedIn Golden Badges for Research Skills, Interpersonal Skills, Critical Thinking, and Teamwork—signaling a well-rounded approach to both individual contribution and team collaboration. Graduating with an MCA from Chandigarh University in 2023, I’ve continued to fuel my curiosity by writing technical articles and sharing practical MERN stack insights across platforms. Whether it’s building polished UIs, optimizing backend performance, or guiding a mentee through their first pull request, I’m driven by the power of community and continuous learning. Let’s connect! I'm open to collaborations, mentorship, or building something impactful together. Reach out to me at kumaripayal7488@gmail.com or visit my profile on Topmate.io.